剑指offer 26. 二叉搜索树与双向链表 & leetcode 剑指 Offer 36. 二叉搜索树与双向链表

26. 二叉搜索树与双向链表 & 剑指 Offer 36. 二叉搜索树与双向链表

题目描述

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

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

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

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

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

思路一：

1. 非递归中序遍历二叉树

2. 两个指针，一个指向前一个结点，一个指向当前结点，

3. 前一个指针的右指针指向当前结点，当前结点的左指针指向前一个节点（不要漏了这行，因为不是所有的left指针都指向上个结点，比如上面的4和3，就需要手动将4结点的left指针指向3），

4. pre后移

5. 头尾相接

 1 class Solution {
 2 
 3     public Node treeToDoublyList(Node root) {
 4         // 非递归中序遍历
 5         if(root == null){
 6             return root;
 7         }
 8         Stack<Node> stack = new Stack<>();
 9         Node head = null, pre = null, cur = root;
10         while(!stack.isEmpty() || cur != null){
11             while(cur != null){
12                 stack.push(cur);
13                 cur = cur.left;
14             }
15             cur = stack.pop();
16             if(pre == null){
17                 head = cur;
18             }else{
19                 pre.right = cur;
20                 cur.left = pre;     // 不要漏了这行，因为不是所有的left指针都指向上个结点
21             }
22             pre = cur;
23             cur = cur.right;
24         }
25         // 首尾相接
26         head.left = pre;
27         pre.right = head;
28         return head;
29     }
30 }

leetcode 运行时间为1 ms > 19.39%, 空间为38.2 MB > 88.58%

复杂度分析：

时间复杂度：使用非递归中序遍历遍历了整棵树，所以时间复杂度为O(n)

空间复杂度：需要一个栈，栈的大小最大为树的高度，树高最大为O(n), 最小为O(logn), 所以空间复杂度最好为O(logn), 最差为O(n)

思路二：递归非中序遍历

思路参考：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/solution/mian-shi-ti-36-er-cha-sou-suo-shu-yu-shuang-xian-5/

把 head、pre 指针定义成全局变量，可以省去如何递归之间传递指针的思考

 1 class Solution {
 2 
 3     Node head = null, pre = null;
 4 
 5     public Node treeToDoublyList(Node root) {
 6         // 递归中序遍历
 7         if(root == null){
 8             return null;
 9         }
10         midOrder(root);
11         // 首尾相接
12         head.left = pre;
13         pre.right = head;
14         return head;
15     }
16 
17     public void midOrder(Node root){
18         if(root == null){
19             return ;
20         }
21         midOrder(root.left);
22         if(head == null){
23             head = root;
24         }else{
25             pre.right = root;
26         }
27         root.left = pre;
28         pre = root;
29         midOrder(root.right);
30     }
31 }

leetcode 运行时间为0 ms > 100.00%, 空间为38.4 MB > 56.50%

复杂度分析：

时间复杂度：使用递归中序遍历遍历了整棵树，所以时间复杂度为O(n)

空间复杂度：需要一个递归栈，栈的大小最大为树的高度，树高最大为O(n), 最小为O(logn), 所以空间复杂度最好为O(logn), 最差为O(n)

思路三：

1. 中序递归遍历二叉树，把所有结点都存下来

2. 把数组中的结点链接成一个双向链表

 1 class Solution {
 2 
 3     public Node treeToDoublyList(Node root) {
 4         // 使用递归中序遍历把结点都存在一个集合中，然后遍历集合，修改每个结点的指向
 5         if(root == null){
 6             return null;
 7         }
 8 
 9         ArrayList<Node> list = new ArrayList<>();
10 
11         midOrder(root, list);
12         for(int i = 0;  i < list.size() - 1; i++){
13             list.get(i).right = list.get(i+1);
14             list.get(i+1).left = list.get(i);
15         }
16         // 首尾相接
17         list.get(0).left = list.get(list.size()-1);
18         list.get(list.size()-1).right = list.get(0);
19         return list.get(0);
20     }
21 
22     public void midOrder(Node root, ArrayList<Node> list){
23         if(root == null){
24             return ;
25         }
26         midOrder(root.left, list);
27         list.add(root);
28         midOrder(root.right, list);
29     }
30 }

leetcode 运行时间为1 ms > 19.39%, 空间为38.7 MB > 16.49%

复杂度分析：

时间复杂度：首先使用递归中序遍历遍历了整棵树，花费的时间为O(n)，随后遍历存储了所有结点的集合，花费的时间也为O(n), 所以整体时间复杂度为O(2n)

空间复杂度：首先递归遍历需要一个递归栈，栈的大小最大为树的高度，树高最大为O(n), 最小为O(logn), 所以花费的空间最少为为O(logn), 最多为O(n)；其次需要一个集合存储所有结点，需要O(n)的空间，所以整体的空间复杂度为O(2n)