二叉搜索樹中的兩個節(jié)點被錯誤地交換堂油。
請在不改變其結構的情況下赶掖，恢復這棵樹竿裂。
示例 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) 空間復雜度的解法很容易實現许帐。
你能想出一個只使用常數空間的解決方案嗎？
思路：
不考慮常數空間復雜度則使用中序遍歷就好主经，如果要用常數空間復雜度則需要使用二叉線索樹荣暮，樹的右指針指向下一個節(jié)點，首先從根節(jié)點往前構建線索罩驻，然后在順著線索往后遍歷進行判斷穗酥，具體看代碼。
代碼：
/**
* 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é)點沒有左子樹惠遏，則不需要構建線索
if (cur.left == null){
detect(pre, cur);
pre = cur;
cur = cur.right;
}
else {
// 左指針節(jié)點比根節(jié)點小砾跃，構建線索要往前，所以當根節(jié)點線索完成后需要創(chuàng)建左指針節(jié)點的線索
TreeNode node = cur.left;
// 找到左指針節(jié)點的最右節(jié)點节吮，這是根節(jié)點的前一個節(jié)點
while (node.right != null && node.right != cur) node = node.right;
// 創(chuàng)建線索
if (node.right == null){
node.right = cur;
cur = cur.left;
}
// 如果線索已經存在抽高，需要進行二叉搜索樹判斷，并把線索去掉
else {
detect(pre, cur);
pre = cur;
cur = cur.right;
// 去掉線索
node.right = null;
}
}
}
//交換錯誤的兩個節(jié)點的值
if (first != null && second != null) {
first.val = first.val + second.val;
second.val = first.val - second.val;
first.val -= second.val;
}
}
// 監(jiān)測是否符合二叉搜索樹
private void detect(TreeNode pre, TreeNode cur){
if (pre != null && pre.val > cur.val){
if (first == null) first = pre;
second = cur;
}
}
}
