[閒聊] 每日leetcode 75 - Day24

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 } } --
※ 批踢踢實業坊(ptt.cc), 來自: 60.248.143.172 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1751868911.A.EB8.html