二叉搜索樹中的兩個(gè)節(jié)點(diǎn)被錯(cuò)誤地交換。

請(qǐng)?jiān)诓桓淖兤浣Y(jié)構(gòu)的情況下，恢復(fù)這棵樹。

示例 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

進(jìn)階:
使用 O(n) 空間復(fù)雜度的解法很容易實(shí)現(xiàn)。
你能想出一個(gè)只使用常數(shù)空間的解決方案嗎？

思路：

不考慮常數(shù)空間復(fù)雜度則使用中序遍歷就好，如果要用常數(shù)空間復(fù)雜度則需要使用二叉線索樹，樹的右指針指向下一個(gè)節(jié)點(diǎn)，首先從根節(jié)點(diǎn)往前構(gòu)建線索，然后在順著線索往后遍歷進(jìn)行判斷，具體看代碼。

代碼：

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {

    TreeNode first,second;

    public void recoverTree(TreeNode root) {
        TreeNode cur = root, pre = null;
        while (cur != null){
            // 如果該子樹根節(jié)點(diǎn)沒有左子樹，則不需要構(gòu)建線索
            if (cur.left == null){
                detect(pre, cur);
                pre = cur;
                cur = cur.right;
            }
            else {
                // 左指針節(jié)點(diǎn)比根節(jié)點(diǎn)小，構(gòu)建線索要往前，所以當(dāng)根節(jié)點(diǎn)線索完成后需要?jiǎng)?chuàng)建左指針節(jié)點(diǎn)的線索
                TreeNode node = cur.left;
                // 找到左指針節(jié)點(diǎn)的最右節(jié)點(diǎn)，這是根節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
                while (node.right != null && node.right != cur) node = node.right;
                // 創(chuàng)建線索
                if (node.right == null){
                    node.right = cur;
                    cur = cur.left;
                }
                // 如果線索已經(jīng)存在，需要進(jìn)行二叉搜索樹判斷，并把線索去掉
                else {
                    detect(pre, cur);
                    pre = cur;
                    cur = cur.right;
                    // 去掉線索
                    node.right = null;
                }
            }
        }
        //交換錯(cuò)誤的兩個(gè)節(jié)點(diǎn)的值
        if (first != null && second != null) {
            first.val = first.val + second.val;
            second.val = first.val - second.val;
            first.val -= second.val;
        }
    }

    // 監(jiān)測(cè)是否符合二叉搜索樹
    private void detect(TreeNode pre, TreeNode cur){
        if (pre != null && pre.val > cur.val){
            if (first == null) first = pre;
            second = cur;
        }
    }
}