题目信息

  • 题目：剑指 Offer 36. 二叉搜索树与双向链表

  • 时间： 2020-09-05

  • 题目链接：Leetcode

  • tag： 二叉搜索树 中序遍历 递归 深度优先搜索

  • 难易程度：中等

  • 题目描述：

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

示例:

1
2
3
4
5
    4
   / \
  2   5
 / \   
1  3

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

提示

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

解题思路

本题难点

二叉搜索树 转换成一个 “排序的循环双向链表” ，其中包含三个要素：

  • 排序链表： 节点应从小到大排序，因此应使用 中序遍历 “从小到大”访问树的节点；

  • 双向链表： 在构建相邻节点（设前驱节点 pre ，当前节点 cur ）关系时，不仅应 pre.right=cur ，也应 cur.left=pre 。

  • 循环链表： 设链表头节点 head 和尾节点 tail ，则应构建 head.left=tail 和 tail.right=head 。

具体思路

二叉搜索树的中序遍历为 递增序列 。

  • 中序遍历：

    1
    2
    3
    4
    5
    6
    void dfs(TreeNode root) {
        if(root == null) return;
        dfs(root.left); // 左
        System.out.println(root.val); // 根
        dfs(root.right); // 右
    }

根据以上分析，考虑使用中序遍历访问树的各节点 cur ；并在访问每个节点时构建 cur 和前驱节点 pre 的引用指向；中序遍历完成后，最后构建头节点和尾节点的引用指向即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
    //pre本来是前序节点，随着中序遍历，最终会成为中序遍历的尾节点
    //head指向中序遍历的头节点
    Node pre,head;
    public Node treeToDoublyList(Node root) {
        if(root == null){
            return null;
        }
        //深度优先搜索二叉搜索树
        dfs(root);
        //将头节点head的左指针指向尾节点pre
        head.left = pre;
        //将尾节点pre的左指针指向头节点head
        pre.right = head;
        //返回结果
        return head;

    }

    void dfs(Node cur){
      //终止条件： 当节点 cur 为空，代表越过叶节点，直接返回；
        if(cur == null){
            return;
        }
        //递归遍历左子树
        dfs(cur.left);
        //当前节点cur不存在左子树时，此时cur无前驱节点，即前驱节点pre==null，cur为中序遍历的第一个节点
        if(pre == null){
            //将中序遍历的头节点cur赋予双向链表的头节点head
            head = cur;
        }else{
            //当前节点cur存在前置节点pre,将pre的右指针指向cur
            pre.right = cur;
            //当前节点cur存在前驱节点pre,将cur的左指针指向pre，形成双向链表
        		cur.left = pre;
        }
        //将前驱节点pre后移，保存当前节点cur
        pre = cur;
        //递归遍历右子树
        dfs(cur.right); 
    }
}

复杂度分析：

  • 时间复杂度 O(N) ： N 为二叉树的节点数，中序遍历需要访问所有节点。
  • 空间复杂度 O(N) ： 最差情况下，即树退化为链表时，递归深度达到 N，系统使用 O(N) 栈空间。

其他优秀解答

解题思路

中序遍历的非递归，使用栈的先进后出特性。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public Node treeToDoublyList(Node root) {
        if(root == null){
            return null;
        }
  			//用栈实现
         Stack<Node> stack = new Stack<>();
         Node current = root;
         Node pre = null, head = null;
         while(!stack.isEmpty() || current != null) {
           //内层循环将当前数据入栈
             while(current != null) {
                 stack.push(current);
                 current = current.left;
             }
           //出栈并将该元素放入到链表中
             current = stack.pop();
             if(pre == null) {//处理头结点
                 head = current;
             }else {
                 pre.right = current;
                 current.left = pre;
             }
            pre = current;
           ////将cur指向栈顶元素的右孩子
            current = current.right;
         }
         pre.right = head;
         head.left = pre;
         return head;
    }