450. Delete Node in a BST

source: https://leetcode.com/problems/add-strings/

Question

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

Search for a node to remove. If the node is found, delete the node.

思路

这道题拿到手上之后，我的第一反应是去用traverse的模版去做，类似：

function traverse(root) {
    if (root == null) return;
    traverse(root.left);
    // do something
    callback(root.val);
    traverse(root.right);
}

这么做其实也是可以做出来的，但是会更加的复杂，因为要去考虑父节点和子节点之间的关系。更好的办法是去用修改的bst模版去做：

function operate(root) {
  if (root == null) return null;
  root.left = operate(root.left);
  root.right = operate(root.right);
  return root;
}

这种范式是有返回值的，优点是可以仅考虑本节点的情况。

本题中，对于本节点的操作有这么几种可能性：

恰好是末端节点，两个子节点都为空，直接删掉就行
只有一个非空子节点。如果是左节点，用左节点中的最大节点替换；如果是右节点，用右节点中的最小节点替换
有两个非空子节点，用只有一个非空子节点其中的一种情况来处理即可

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  /**
   * 找到本节点下的最左节点
   * - 在BST下即为最小节点
   */
  fn node_min(root: &Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
      let mut left = root.clone();
      let mut stop = false;
      while !stop {
          // 这里有个前提，传进来的root一定不为空
          let l = left.clone().unwrap().borrow_mut().left.clone();
          if l.is_some() {
              left = l;
          } else {
              stop = true;
          }
      }
      left.clone()
  }

  /**
   * 找到本节点下的最右节点
   * - 在BST下即为最大节点
   */
  fn node_max(root: &Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
      let mut right = root.clone();
      let mut stop = false;
      while !stop {
          // 这里有个前提，传进来的root一定不为空
          let r = right.clone().unwrap().borrow_mut().right.clone();
          if r.is_some() {
              right = r;
          } else {
              stop = true;
          }
      }
      right.clone()
  }

  pub fn delete_node(root: Option<Rc<RefCell<TreeNode>>>, key: i32) -> Option<Rc<RefCell<TreeNode>>> {
      if let Some(n) = root.clone() {
          let left = n.borrow_mut().left.clone();
          let right = n.borrow_mut().right.clone();
          let val = n.borrow().val;
          // 如果为目标节点
          if val == key {
              // 恰好是末端节点，两个子节点都为空，直接删掉就行
              if left.is_none() && right.is_none() {
                  return None;
              // 有右节点，用右节点中的最小节点替换
              } else if right.is_some() {
                  // 找出右节点中的最小节点值。此处右节点一定不为空
                  let min_val = Self::node_min(&right).unwrap().borrow().val;
                  // 把本节点的值替换掉
                  n.borrow_mut().val = min_val;
                  // 删去右节点中的最小节点
                  n.borrow_mut().right = Self::delete_node(right, min_val);
              // 有左节点，用左节点中的最大节点替换
              } else {
                  // 找出左节点中的最大节点值。此处左节点一定不为空
                  let max_val = Self::node_max(&left).unwrap().borrow().val;
                  // 把本节点的值替换掉
                  n.borrow_mut().val = max_val;
                  // 删去左节点中的最大节点
                  n.borrow_mut().left = Self::delete_node(left, max_val);
              }
          // 比目标节点值大，目标节点在左节点处
          } else if val > key {
              n.borrow_mut().left = Self::delete_node(left, key);
          // 比目标节点值小，目标节点在右节点处
          } else if val < key {
              n.borrow_mut().right = Self::delete_node(right, key);
          }
          // 返回当前节点
          return root.clone();
      }
      return None;
  }
}

End

这一道题比预想的要不好做一点，可能是没有掌握操作节点的一点诀窍，仍然用了遍历的思路去做。

对于不同的问题，要用不同的范式去做。

Bert Huang

450. Delete Node in a BST

Question

思路

End