1
2
3

输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。

1
2
3

输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

// @lc code=start
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    /// ## 解题思路
    /// - 递归
    /// 1. 二叉搜索树进行中序遍历时, 各节点值将保持顺序递增, 即node[i].val < node[i+1].val;
    /// 2. 如果有两个节点进行了交换, 则交换的两个节点值与周围节点将不满足顺序递增的关系;
    ///    假设交换前的两个节点node1, node2, 有 node1.val< node1.1.val < .. < node2.0.val < node2.val,
    ///    则交换后, [(node2.val) > node1.1.val] < .. < [node2.0.val > (node1.val)]
    /// 3. 所以, 中序遍历树时, 检查当前节点和前一个节点的大小关系,
    ///    当出现了第一次逆序, 则记录前一个节点node1,
    ///    出现第二次逆序时, 记录后一个节点node2,
    ///    之后交换node1, node2的值
    /// 4. 当被交换的两个节点node1, node2挨着时, 之后出现一次逆序情况,
    ///    此时直接记录node1为前一个节点, node2为后一个节点, 综合3,4两种情况,
    ///    则当发生逆序时, 逆序前一个节点只须更新一次, 后一个节点必须每次都更新;
    pub fn recover_tree(root: &mut Option<Rc<RefCell<TreeNode>>>) {
        /// 查找逆序节点对
        fn find_unorder_pairs(
            root: &Option<Rc<RefCell<TreeNode>>>,
            prev: &mut Option<Rc<RefCell<TreeNode>>>,
            unorder_pairs: &mut (Option<Rc<RefCell<TreeNode>>>, Option<Rc<RefCell<TreeNode>>>),
        ) {
            if let Some(node) = root {
                let node = node.borrow();

                // 递归处理当前节点左子树
                find_unorder_pairs(&node.left, prev, unorder_pairs);

                // 处理当前节点
                match prev {
                    // 出现了逆序节点
                    Some(prev1) if prev1.borrow().val > node.val => {
                        if unorder_pairs.0.is_none() {
                            //node1只更新一次记录
                            unorder_pairs.0 = prev.clone();
                        }
                        // node2每次都得更新记录
                        unorder_pairs.1 = root.clone();
                    }
                    _ => {}
                }
                *prev = root.clone();

                // 递归处理当前节点左子树
                find_unorder_pairs(&node.right, prev, unorder_pairs);
            }
        }

        let mut pairs = (None, None);
        find_unorder_pairs(root, &mut None, &mut pairs);
        if let (Some(mut node1), Some(mut node2)) = pairs {
            std::mem::swap(&mut node1.borrow_mut().val, &mut node2.borrow_mut().val);
        }
    }
}
// @lc code=end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

class Solution {
    /* 递归遍历时的环境变量 */
    TreeNode *prev;  //当前节点前一个节点
    TreeNode *node1; //逆序开始节点
    TreeNode *node2; //逆序最后节点
public:
    /**
     * ## 解题思路
     * 1. 中序遍历二叉搜索树，正常的二叉搜索树为有序递增序列；
     * 2. 乱序的两个节点之间的所有节点为逆序排列；
     * 3. 遍历时，根据当前节点和前一个节点的大小关系，判断是否逆序；
     * 4. 使用两个临时节点变量分别记录逆序的开始和结束；
     * 5. 遍历完成后，交换逆序开始和结束节点；
     */
    void recoverTree(TreeNode* root) {
        inorder(root);
        swap(node1->val, node2->val);
    }

    // 中序遍历二叉树
    void inorder(TreeNode* node) {
        //节点为nil，结束遍历
        if (!node) {
            return;
        }
        //递归中序遍历左子树
        inorder(node->left);

        //处理当前节点

        // 如果当前节点和前一个节点逆序
        if (prev && node->val < prev->val) {
            if (!node1) {       //第一个逆序节点为开始节点
                node1 = prev;
            }
            node2 = node;     //逆序结束节点
        }

        //当前节点处理完后，保存当前节点为上一个节点
        prev = node;

        //递归中序遍历右子树
        inorder(node->right);
    }
};
void swap(int &a, int& b) {
    a ^= b;
    b ^= a;
    a ^= b;
}