36-二叉搜索树与双向链表

题目描述

https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

为了让您更好地理解问题，以下面的二叉搜索树为例：

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

注意：本题与主站 426 题相同：https://leetcode.cn/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/

注意：此题对比原题有改动。

思路分析

如果树有节点，则拍扁的时候，将子节点插入上面的两个节点中间

基本思路：中序遍历：左根右，最左边的就是 head

实现代码

csharp

/*
// Definition for a Node.
public class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
        left = null;
        right = null;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
}
*/

public class Solution {
    
    private Node pre;  //前一个节点
    private Node head; //头节点

    private void dfs(Node cur){
        if(cur == null){
            return;
        }
        //往左递归，就是最小的那个
        dfs(cur.left);
        //第一次满足条件， head 为空，当前就是 head
        if(head == null){
            head = cur;
        }
        if(pre != null){
            pre.right = cur;
            cur.left = pre;
        }
        pre = cur;
        dfs(cur.right);
    }


    public Node TreeToDoublyList(Node root) {
        //边界值
        if(root == null){
            return null;
        }
        dfs(root);
        //题目要求
        head.left = pre;
        pre.right = head;
        return head;
    }
}

错误代码参考

出错示例：[28,-98,67,null,-89,62,null,-97,-25,null,64,null,null,-72,-9,null,null,-88,-41,null,-7,null,-78,-53,null,null,2,-85,-77,-69,-42,-1]

        28
      /   \
    -98    67
       \
        -89

csharp


public class Solution {

    private Node head = null;

    private Node dfs(Node root){
        if(root == null){
            return null;
        }
        Node cur = dfs(root.left);
        Console.Write("{0} ",root.val);
        //头节点
        if(head == null){
            head = root;
        }
        if(cur != null){
            //找出他最后一个节点(此处不对 cur.right 第一次遍历的时候，就可能有值了，应该是他自己)
            //比如上图遍历到 98 的时候他的最右节点应该是自己，但是这里却返回了 -89 他之前本来就有的最右节点，所以出错了。
            // 836
            cur.right = root;            
            root.left = cur;
        }
        //注意：这里其实dfs的时候不需要返回左边的节点来处理，直接用 root 作为当前节点，参考下面复习代码

        Node temp = dfs(root.right);
        if(temp != null){
            temp.left = root;
        }
        return root;
    }

    public Node TreeToDoublyList(Node root) {
        if(root == null){
            return null;
        }
        dfs(root);
        //链接首尾
        Node cur = root;
        while(cur.right != null){
            cur = cur.right;
        }
        cur.right = head;
        head.left = cur;
        return head;
    }
}

复习：20220508

csharp

public class Solution {
    private Node head;
    private Node pre;
    private void dfs(Node root){
        if(root == null){
            return;
        }
        dfs(root.left);
        //处理头结点     
        if(head == null){ //如果头指针为空，说明找到了最左边的子节点，设置为头指针
            head = root;
        }
        else{ //头指针找到了后，必然会开始设置前驱节点，所以当 head != null 的时候，pre 必然有值，所以开始设置前驱节点
            pre.right = root;
            root.left = pre;
        }
        //设置 pre 下个循环有用
        pre = root;
        dfs(root.right);
    }

    public Node TreeToDoublyList(Node root) {
        if(root == null){
            return null;
        }
        dfs(root);
        // 最后按照题意组合收尾相连，此时 pre 就是最后一个指针
        pre.right = head;
        head.left = pre;
        return head;
    }
}

Morris遍历

csharp

public class Solution {
    public Node TreeToDoublyList(Node root){
        if(root == null){
            return null;
        }
        Node cur = root; 
        Node mostRight = null; //morris 的最右指针
        Node head = root; //头指针，最后会一直指向到最左边
        Node pre = null; //前一个指针

        //先找出最左指针
        while(head.left != null){
            head = head.left;
        }

        while(cur != null){
            mostRight = cur.left;
            if(mostRight != null){
                while(mostRight.right != null && mostRight.right != cur){
                    mostRight = mostRight.right;
                }

                if(mostRight.right == null){ //建立连接
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }
            }

            Node now = cur; //记录遍历过的节点
            cur = cur.right; //必须先将cur指向下一个节点
            if(pre != null){
                now.left = pre;
                pre.right = now;
            }
            pre = now;
        
        }
        //最后收尾相连
        pre.right = head;
        head.left = pre;
        return head;

    }
}

复习：20220611

csharp

public class Solution {

    private Node pre = null;
    private Node head = null;

    private void dfs(Node root){
        if(root == null){
            return;
        }
        dfs(root.left);
        if(head == null){
            head = root;
        }
        if(pre != null){
            root.left = pre;
            pre.right = root;
        }
        pre = root;
        dfs(root.right);
    }

    public Node TreeToDoublyList(Node root) {
        if(root == null){
            return null;
        }
        dfs(root);
        head.left = pre;
        pre.right = head;
        return head;
    }
}

36-二叉搜索树与双向链表 #

题目描述 #

思路分析 #

实现代码 #

错误代码参考 #

复习：20220508 #

Morris遍历 #

复习：20220611 #

36-二叉搜索树与双向链表

题目描述

思路分析

实现代码

错误代码参考

复习：20220508

Morris遍历

复习：20220611