99. Recover Binary Search Tree Medium

1/**
2 * [99] Recover Binary Search Tree
3 *
4 * You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.
5 *  
6 * Example 1:
7 * <img alt="" src="https://assets.leetcode.com/uploads/2020/10/28/recover1.jpg" style="width: 422px; height: 302px;" />
8 * Input: root = [1,3,null,null,2]
9 * Output: [3,1,null,null,2]
10 * Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.
11 * 
12 * Example 2:
13 * <img alt="" src="https://assets.leetcode.com/uploads/2020/10/28/recover2.jpg" style="width: 581px; height: 302px;" />
14 * Input: root = [3,1,4,null,null,2]
15 * Output: [2,1,4,null,null,3]
16 * Explanation: 2 cannot be in the right subtree of 3 because 2 < 3. Swapping 2 and 3 makes the BST valid.
17 * 
18 *  
19 * Constraints:
20 * 
21 * The number of nodes in the tree is in the range [2, 1000].
22 * -2^31 <= Node.val <= 2^31 - 1
23 * 
24 *  
25 * Follow up: A solution using O(n) space is pretty straight-forward. Could you devise a constant O(1) space solution?
26 */
27pub struct Solution {}
28#[allow(unused_imports)]
29use crate::util::tree::{TreeNode, to_tree};
30
31// problem: https://leetcode.com/problems/recover-binary-search-tree/
32// discuss: https://leetcode.com/problems/recover-binary-search-tree/discuss/?currentPage=1&orderBy=most_votes&query=
33
34// submission codes start here
35
36// Definition for a binary tree node.
37// #[derive(Debug, PartialEq, Eq)]
38// pub struct TreeNode {
39//   pub val: i32,
40//   pub left: Option<Rc<RefCell<TreeNode>>>,
41//   pub right: Option<Rc<RefCell<TreeNode>>>,
42// }
43// 
44// impl TreeNode {
45//   #[inline]
46//   pub fn new(val: i32) -> Self {
47//     TreeNode {
48//       val,
49//       left: None,
50//       right: None
51//     }
52//   }
53// }
54use std::rc::Rc;
55use std::cell::RefCell;
56use std::mem::swap;
57type Node = Option<Rc<RefCell<TreeNode>>>;
58impl Solution {
59    pub fn recover_tree(root: &mut Node) {
60        let (mut first, mut second, mut pre) = (None, None, None);
61        Self::dfs(root, &mut first, &mut second, &mut pre);
62        swap(
63            &mut first.unwrap().borrow_mut().val,
64            &mut second.unwrap().borrow_mut().val,
65        );
66    }
67
68    fn dfs(node: &Node, first: &mut Node, second: &mut Node, pre: &mut Node) {
69        if let Some(n) = node {
70            let r = n.as_ref().borrow();
71            Self::dfs(&r.left, first, second, pre);
72            if let Some(p) = pre {
73                if p.as_ref().borrow().val >= r.val {
74                    if first.is_none() {
75                        *first = Some(p.clone());
76                    }
77                    if first.is_some() {
78                        *second = Some(n.clone());
79                    }
80                }
81            }
82            *pre = Some(n.clone());
83            Self::dfs(&r.right, first, second, pre)
84        }
85    }
86}
87
88// submission codes end
89
90#[cfg(test)]
91mod tests {
92    use super::*;
93    use crate::tree;
94
95    #[test]
96    fn test_99() {
97        Solution::recover_tree(&mut tree![1,3,2]);
98    }
99}
100