Java實作 LeetCode 99 恢複二叉搜尋樹

99. 恢複二叉搜尋樹

二叉搜尋樹中的兩個節點被錯誤地交換。

請在不改變其結構的情況下，恢複這棵樹。

示例 1:

輸入: [1,3,null,null,2]

1
  /
 3
  \
   2
      

輸出: [3,1,null,null,2]

3
  /
 1
  \
   2
      

示例 2:

輸入: [3,1,4,null,null,2]

3
 / \
1   4
   /
  2
      

輸出: [2,1,4,null,null,3]

2
 / \
1   4
   /
  3
      

進階:

使用 O(n) 空間複雜度的解法很容易實作。

你能想出一個隻使用常數空間的解決方案嗎？

PS：

中序周遊過程中，記錄錯誤兩個錯誤排序節點，最後進行交換

隻需要中序周遊一遍就可以了

首先我們來看中序周遊過程模闆

public void inorder(TreeNode root){
        if (root == null) return ;    //終止條件
        inorder(root.left);           //通路左子樹
        對目前節點進行一些操作          //通路根節點-----在周遊過程中希望實作的操作
        inorder(root.right);          //通路右子樹
    }
      

另一方面我們知道 對二叉搜尋樹進行 中序周遊的時候 通路到的元素是從小到大順序排列的

如我們對執行個體 2 恢複好的樹 進行中序周遊 得到的應該是 1 2 3 4

那這道題我們就有了大緻思路

我們對錯誤的二叉樹進行 中序周遊 那我們按順序通路到的數應該是按順序排列的

那如果對兩個節點交換了順序 那一定有兩個地方是 不滿足 前一個元素 < 目前元素 < 後一個元素

如示例2 3 1 4 2：

3 這個節點不滿足 1 這個節點不滿足

是以我們使用兩個全局變量在周遊過程中記錄這兩個節點 最後對他們進行交換

class Solution {

 
    TreeNode t1, t2, pre;
    public void recoverTree(TreeNode root) {
        inorder(root);
        int temp = t1.val;
        t1.val = t2.val;
        t2.val = temp;
    }
    public void inorder(TreeNode root){
        if (root == null) return ;
        inorder(root.left);
        if (pre != null && pre.val > root.val) {
            if (t1 == null) t1 = pre;
            t2 = root;
        }
        pre = root;
        inorder(root.right);
    }
}
      

1
  /
 3
  \
   2
      

3
  /
 1
  \
   2
      

3
 / \
1   4
   /
  2
      

2
 / \
1   4
   /
  3
      

public void inorder(TreeNode root){
        if (root == null) return ;    //終止條件
        inorder(root.left);           //通路左子樹
        對目前節點進行一些操作          //通路根節點-----在周遊過程中希望實作的操作
        inorder(root.right);          //通路右子樹
    }
      

class Solution {

 
    TreeNode t1, t2, pre;
    public void recoverTree(TreeNode root) {
        inorder(root);
        int temp = t1.val;
        t1.val = t2.val;
        t2.val = temp;
    }
    public void inorder(TreeNode root){
        if (root == null) return ;
        inorder(root.left);
        if (pre != null && pre.val > root.val) {
            if (t1 == null) t1 = pre;
            t2 = root;
        }
        pre = root;
        inorder(root.right);
    }
}