450. Delete Node in a BST
题目：
删除二元树的某节点
思路：
这一题可以用 in-order successor 来替换
我们把要删除的节点替换成右边子树的最小值
(右边子树的最左边)
然后删除这个叶节点
整体流程其实就是二元搜寻
只是找到之后多做一个删除
删除的时候判断左右
1. 都是空 -> 回传 None
2. 只有左/右 -> 回传左/右
3. 有左右 -> 用 in-order successor 替换
然后再跑一次把这个叶节点做 1. 的删除
Code:
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
pub fn delete_node(
root: Option<Rc<RefCell<TreeNode>>>,
key: i32,
) -> Option<Rc<RefCell<TreeNode>>> {
match root {
Some(node) => {
let cloned = node.clone();
let mut n = cloned.borrow_mut();
if n.val > key {
n.left = Self::delete_node(n.left.clone(), key);
Some(node)
} else if n.val < key {
n.right = Self::delete_node(n.right.clone(), key);
Some(node)
} else {
if n.left.is_none() && n.right.is_none() {
return None;
}
if n.left.is_none() {
return n.right.clone();
}
if n.right.is_none() {
return n.left.clone();
}
let succesor = Self::find_min(n.right.clone());
n.val = succesor.unwrap().borrow().val;
n.right = Self::delete_node(n.right.clone(), n.val);
Some(node)
}
}
None => None,
}
}
fn find_min(mut node: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<
TreeNode>>> {
while let Some(n) = node.clone() {
if n.borrow().left == None {
return node.clone();
}
node = n.borrow().left.clone();
}
None
}
}