[Leetcode][第99题][JAVA][恢复二叉搜索树][中序遍历]

亦凉 2022-11-25 10:27 114阅读 0赞

#### 【问题描述】\[困难\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]

#### 【解答思路】 ####

###### 1. 显示中序遍历 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]

**时间复杂度：O(N) 空间复杂度：O(N)**

class Solution { 
        public void recoverTree(TreeNode root) { 
            List<Integer> nums = new ArrayList<Integer>();
            inorder(root, nums);
            int[] swapped = findTwoSwapped(nums);
            recover(root, 2, swapped[0], swapped[1]);
        }
    
        public void inorder(TreeNode root, List<Integer> nums) { 
            if (root == null) { 
                return;
            }
            inorder(root.left, nums);
            nums.add(root.val);
            inorder(root.right, nums);
        }
    
        public int[] findTwoSwapped(List<Integer> nums) { 
            int n = nums.size();
            //第一次找到取前面 第二次找到取后面
            int x = -1, y = -1;
            for (int i = 0; i < n - 1; ++i) { 
                if (nums.get(i + 1) < nums.get(i)) { 
                    y = nums.get(i + 1);
                    if (x == -1) { 
                        x = nums.get(i);
                    } else { 
                        break;
                    }
                }
            }
            return new int[]{ x, y};
        }
    
        public void recover(TreeNode root, int count, int x, int y) { 
            if (root != null) { 
                if (root.val == x || root.val == y) { 
                    root.val = root.val == x ? y : x;
                    if (--count == 0) { 
                        return;
                    }
                }
                recover(root.right, count, x, y);
                recover(root.left, count, x, y);
            }
        }
    }

###### 2. 隐式中序遍历 栈 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][2020080811490824.png]

**时间复杂度：O(N) 空间复杂度：O(H)**  
![在这里插入图片描述][20200808114827346.png]

class Solution { 
        public void recoverTree(TreeNode root) { 
            Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
            TreeNode x = null, y = null, pred = null;
    
            while (!stack.isEmpty() || root != null) { 
                while (root != null) { 
                    stack.push(root);
                    root = root.left;
                }
                root = stack.pop();
                if (pred != null && root.val < pred.val) { 
                    y = root;
                    if (x == null) { 
                        x = pred;
                    } else { 
                        break;
                    }
                }
                pred = root;
                root = root.right;
            }
    
            swap(x, y);
        }
    
        public void swap(TreeNode x, TreeNode y) { 
            int tmp = x.val;
            x.val = y.val;
            y.val = tmp;
        }
    }

###### 3. Morris 中序遍历 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 7]

**时间复杂度：O(N) 空间复杂度：O(1)**  
![在这里插入图片描述][20200808115239892.png]

class Solution { 
        public void recoverTree(TreeNode root) { 
            TreeNode x = null, y = null, pred = null, predecessor = null;
    
            while (root != null) { 
                if (root.left != null) { 
                    // predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
                    predecessor = root.left;
                    while (predecessor.right != null && predecessor.right != root) { 
                        predecessor = predecessor.right;
                    }
                    
                    // 让 predecessor 的右指针指向 root，继续遍历左子树
                    if (predecessor.right == null) { 
                        predecessor.right = root;
                        root = root.left;
                    }
                    // 说明左子树已经访问完了，我们需要断开链接
                    else { 
                        if (pred != null && root.val < pred.val) { 
                            y = root;
                            if (x == null) { 
                                x = pred;
                            }
                        }
                        pred = root;
    
                        predecessor.right = null;
                        root = root.right;
                    }
                }
                // 如果没有左孩子，则直接访问右孩子
                else { 
                    if (pred != null && root.val < pred.val) { 
                        y = root;
                        if (x == null) { 
                            x = pred;
                        }
                    }
                    pred = root;
                    root = root.right;
                }
            }
            swap(x, y);
        }
    
        public void swap(TreeNode x, TreeNode y) { 
            int tmp = x.val;
            x.val = y.val;
            y.val = tmp;
        }
    }

#### 【总结】 ####

###### 1. 交换的思想 ######

两个指针或两个标志找逆序

###### 2. 二叉搜索树 中序遍历 单调递增 ######

###### 3.空间复杂度优化 Morris 中序遍历优化 空间复杂度：O(1) ######

转载链接：https://leetcode-cn.com/problems/recover-binary-search-tree/solution/hui-fu-er-cha-sou-suo-shu-by-leetcode-solution/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: /images/20221124/61e66300ae9c46dc8286ce94756dc6d0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: /images/20221124/951899f0d8e641c6b29e17abf0dd604d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: /images/20221124/213d5816b6044307b65348393cf5a91d.png
[2020080811490824.png]: /images/20221124/6aa2585a025e4f138335981e0384eb6f.png
[20200808114827346.png]: /images/20221124/c170f0b2356c4d24bd393e06c06106ff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]: /images/20221124/8b20194c284146ff99d30fa8b917bc04.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 4]: /images/20221124/197bc3f0579c4e818635482f1176807f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 5]: /images/20221124/2553565e31404a04818c4b807c518e80.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 6]: /images/20221124/85c865b8c36a4e018c05fbcf5941a2f7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 7]: /images/20221124/8ec1a2405f064a689a2deaa279db8bb8.png
[20200808115239892.png]: /images/20221124/d3890501b3fa417cb5a5d6158842a06e.png