701. Insert into a Binary Search Tree

source: https://leetcode.com/problems/insert-into-a-binary-search-tree/

Question

You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Notice that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

思路

插入一个节点，一开始想的比较复杂。去考虑子节点的各种情况，但是如果用递归每层替换去考虑的话，一层层替换下去，最后只要考虑空子节点的情况就好。

pub fn insert_into_bst(root: Option<Rc<RefCell<TreeNode>>>, val: i32) -> Option<Rc<RefCell<TreeNode>>> {
  if let Some(n) = root.clone() {
    let mut n = n.borrow_mut();
    // 比当前节点的值大
    if val > n.val {
      n.right = Self::insert_into_bst(n.right.take(), val);
    // 比当前节点的值小
    } else {
      n.left = Self::insert_into_bst(n.left.take(), val);
    }
    // 返回当前节点
    return root;
  }
  return Some(Rc::from(RefCell::from(TreeNode::new(val))))
}

End

这道题写起来很简单，但是其实想通了不简单。

对于操作bst来说，这题的思想还是很泛用的。