230. 二叉搜索树中第K小的元素

这一题比较简单，就是复习中序遍历，中左右进行遍历之后，直接获取到二叉树的第k个参数即可，对于Rust来说，空间比较难继续优化了

  1. pub fn kth_smallest(root: Option<Rc<RefCell<TreeNode>>>, k: i32) -> i32 {
  2.     let mut list = Vec::<i32>::new();
  3.     Self::dfs_search_tree(root, &mut list);
  4.     list[k as usize]
  5. }
  6. /// 经典的二叉树中序遍历的实现，注意，我们传入的list虽然是vec，是一个指向一块内存的指针
  7. /// 但是实际上还是会被move进去，和所有的struct相同，就算是指针，在我们传递函数的时候是
  8. /// move或者clone的，因此需要使用mut指针来进行传入
  9. fn dfs_search_tree(root: Option<Rc<RefCell<TreeNode>>>, list: &mut Vec<i32>) {
  10.     match root {
  11.         None => { return; }
  12.         Some(node) => {
  13.             // 获取到对于当前节点的RC引用
  14.             let next = Rc::clone(&node);
  15.             // 将树的子结点深拷贝了一份出来，不知道会不会有额外空间开销
  16.             let left = next.borrow().left.clone();
  17.             let right = node.borrow().right.clone();
  19.             Solution::dfs_search_tree(left, list);
  20.             list.push(node.borrow().val);
  21.             Solution::dfs_search_tree(right, list);
  22.         }
  23.     }
  24. }

有一种优化空间的思路，但是奇怪的是，没有优化到空间，时间也多了去了，至少在Rust，Vec的优化是真好

  1. /// 230. 二叉搜索树中第K小的元素
  2. pub fn kth_smallest(root: Option<Rc<RefCell<TreeNode>>>, k: i32) -> i32 {
  3.     let mut ans = 0;
  4.     let mut k= k;
  5.     Self::dfs_search_tree(root, &mut k, &mut ans);
  6.     ans
  7. }
  8. fn dfs_search_tree(root: Option<Rc<RefCell<TreeNode>>>, k: &mut i32, ans: &mut i32) {
  9.     match root {
  10.         None => { return; }
  11.         Some(node) => {
  12.             // 获取到对于当前节点的RC引用
  13.             let next = Rc::clone(&node);
  14.             // 将树的子结点深拷贝了一份出来，不知道会不会有额外空间开销
  15.             let left = next.borrow().left.clone();
  16.             let right = node.borrow().right.clone();
  18.             Solution::dfs_search_tree(left, k, ans);
  19.             // 优化在这里，通过k来进行计数
  20.             *k -= 1;
  21.             if *k == 0 {
  22.                 *ans = node.borrow().val;
  23.             }
  24.             Solution::dfs_search_tree(right, k, ans);
  25.         }
  26.     }
  27. }

java可以这么优化：

  1. class Solution {
  2.     int k, ans;
  3.     public int kthSmallest(TreeNode root, int _k) {
  4.         k = _k;
  5.         dfs(root);
  6.         return ans;
  7.     }
  8.     void dfs(TreeNode root) {
  9.         if (root == null || k <= 0) return ;
  10.         dfs(root.left);
  11.         if (--k == 0) ans = root.val;
  12.         dfs(root.right);
  13.     }
  14. }

关于从RC以及REF中拿取值

性能最好的方法不是clone一个节点出来，确实会造成空间损失，使用borrow_mut直接拿出来value可以得到最小的空间利用率
let left = next.borrow_mut().left.take();

  1. pub fn kth_smallest(root: Option<Rc<RefCell<TreeNode>>>, k: i32) -> i32 {
  2.     let mut list = Vec::<i32>::new();
  3.     Self::dfs_search_tree(root, &mut list);
  4.     list[(k-1) as usize]
  5. }
  6. fn dfs_search_tree(root: Option<Rc<RefCell<TreeNode>>>, list: &mut Vec<i32>) {
  7.     match root {
  8.         None => { return; }
  9.         Some(node) => {
  10.             // 获取到对于当前节点的RC引用
  11.             let next = Rc::clone(&node);
  12.             // 将树的子结点深拷贝了一份出来，不知道会不会有额外空间开销
  13.             let left = next.borrow_mut().left.take();
  14.             let right = node.borrow_mut().right.take();
  16.             Solution::dfs_search_tree(left, list);
  17.             list.push(node.borrow().val);
  18.             Solution::dfs_search_tree(right, list);
  19.         }
  20.     }
  21. }

中序遍历的栈实现

思路就是一直存左，然后左中右

  1. pub fn kth_smallest(root: Option<Rc<RefCell<TreeNode>>>, mut k: i32) -> i32 {
  2.     // 使用一个队列来迭代处理
  3.     let mut queue = Vec::new();
  4.     // 为了能够直接对root进行修改作出的牺牲，但是既然进函数了，所有权就已经不是外面的了
  5.     let mut curr = root;
  7.     while curr.is_some() || !queue.is_empty() {
  8.         // 这里会一直找到最左边元素
  9.         while curr.is_some() {
  10.             queue.push(curr.clone());
  11.             curr = curr.unwrap().borrow().left.clone();
  12.         }   
  13.         // 中的处理，这里注意思考，哪怕是最左边的元素其实也是正确的
  14.         // 就算中节点是空，获取不到右节点，但是后面queue正常pop了
  15.         curr = queue.pop().unwrap();
  16.         k -= 1;
  17.         if k == 0 {
  18.             return curr.unwrap().borrow().val;
  19.         }
  20.         // 走向右节点，注意都是clone，不破坏树
  21.         curr = curr.unwrap().borrow().right.clone();
  22.     }
  24.     k
  25. }

783. 二叉搜索树节点最小距离

1305. 两棵二叉搜索树中的所有元素

这一题的思路比较简单，就是利用二叉搜索树的有序性质直接得到线性表，然后进行合并即可，关键在于进行dfs的时候，需要注意一些用法

  1. use std::rc::Rc;
  2. use std::cell::RefCell;
  3. impl Solution {
  4.     pub fn get_all_elements(root1: Option<Rc<RefCell<TreeNode>>>, root2: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
  5.         // 中序遍历获取所有数据
  6.         fn dfs(root: Option<Rc<RefCell<TreeNode>>>, list: &mut Vec<i32>) {
  7.             match root {
  8.                 None => { return; }
  9.                 // 左中右
  10.                 Some(mut node) => {
  11.                     dfs(node.borrow_mut().left.take(), list);
  12.                     list.push(node.borrow().val);
  13.                     dfs(node.borrow_mut().right.take(), list);
  14.                 }
  15.             }
  16.         }
  17.         let mut ret = Vec::new();
  18.         dfs(root1, &mut ret);
  19.         dfs(root2, &mut ret);
  20.         ret.sort();
  21.         ret
  22.     }
  23. }

另一个就是不用push的思路，直接写有序数组合并的

  1. class Solution {
  2.     int INF = 0x3f3f3f3f;
  3.     public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
  4.         List<Integer> ans = new ArrayList<>();
  5.         List<Integer> l1 = new ArrayList<>(), l2 = new ArrayList<>();
  6.         dfs(root1, l1); dfs(root2, l2);
  7.         int n = l1.size(), m = l2.size(), i = 0, j = 0;
  8.         // 注意三叶写的这里，就很简洁
  9.         while (i < n || j < m) {
  10.             int a = i < n ? l1.get(i) : INF, b = j < m ? l2.get(j) : INF;
  11.             if (a <= b) {
  12.                 ans.add(a); i++;
  13.             } else {
  14.                 ans.add(b); j++;
  15.             }
  16.         }
  17.         return ans;
  18.     }
  19.     void dfs(TreeNode root, List<Integer> list) {
  20.         if (root == null) return ;
  21.         dfs(root.left, list);
  22.         list.add(root.val);
  23.         dfs(root.right, list);
  24.     }
  25. }

449. 序列化和反序列化二叉搜索树

简单来说就是前序遍历直接序列化，反序列化的话，需要考虑到BST的性质，左子树小于root小于右子树，因此就在序列化的数组上面查找刚好大于和小于的位置，作为分界点，使用二分查找优化，但是二分的细节太多了，看代码：

  1. impl Codec {
  2.     fn new() -> Self {
  3.         Self {}
  4.     }
  5.     /// 序列化，简单地前序遍历即可
  6.     fn serialize(&self, root: Option<Rc<RefCell<TreeNode>>>) -> String {
  7.         let mut list = Vec::new();
  8.         self.pre_order(root, &mut list);
  10.         list.into_iter().fold(String::from(""), |acc, x| {
  11.             if acc.len() == 0 {
  12.                 format!("{},", x)
  13.             } else {
  14.                 format!("{},{}", acc, x)
  15.             }
  16.         }).to_string()
  17.     }
  18.     fn pre_order(&self, root: Option<Rc<RefCell<TreeNode>>>, list: &mut Vec<i32>) {
  19.         match root {
  20.             None => { return; }
  21.             Some(mut node) => {
  22.                 let temp = node.borrow_mut().val;
  23.                 list.push(temp);
  24.                 self.pre_order(node.borrow_mut().left.clone(), list);
  25.                 self.pre_order(node.borrow_mut().right.clone(), list);
  26.             }
  27.         }
  28.     }
  30.     fn deserialize(&self, data: String) -> Option<Rc<RefCell<TreeNode>>> {
  31.         if data.is_empty() { return None; }
  32.         let x: Vec<i32> = data.split(",").map(|x: &str| {
  33.             x.parse::<i32>().unwrap()
  34.         }).collect();
  35.         println!("{:?}", x);
  36.         self.construct(0, x.len()-1, &x)
  37.     }
  38.     /// 利用二叉搜索树的特性进行重构，就是左子树小于叶子节点，小于右子树，因此就只需要找到每一个子树
  39.     fn construct(&self, l: usize, r: usize, list: &Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
  40.         if l > r { return None; }
  41.         let (mut ll, mut rr) = (l + 1, r);
  42.         // root节点
  43.         let root_num = list[l];
  44.         let ans = Rc::new(RefCell::new(TreeNode::new(root_num)));
  45.         // 二分查找分界点
  46.         while ll < rr {
  47.             let mid = ll + ((rr - ll) >> 1);
  48.             // 二分这么来分析，大于root的时候右子树，往左找没问题，左二分是l=mid+1
  49.             // 等于的时候，有可能左子树也有可能右子树，关键就在于我们想把这个值放在哪
  50.             // 如果是假设这个值为左子树的话，那么ll=mid+1，使得往右找，相反rr=mid往左
  51.             // 继续
  52.             if list[mid] > root_num { rr = mid; }
  53.             else { ll = mid + 1; }
  54.         }
  55.         // 上面看为了左子树，最后我们rr和ll都是中间结点的位置，还需要继续把相同值左挪
  56.         if list[rr] <= root_num { rr += 1; }
  57.         ans.borrow_mut().left = self.construct(l + 1, rr - 1, list);
  58.         ans.borrow_mut().right = self.construct(rr, r, list);
  59.         Some(ans)
  60.     }
  61. }