Java&C++题解与拓展——leetcode450.删除二叉搜索树中的节点【么的新知识】

• 题目要求
• 思路：递归
• • Java
  • C++
  • Rust【报错】
• 总结

• 根据当前值 k e y key key和 r o o t . v a l root.val root.val的关系删除相应点并更新当前树。
• 更新树的时候可以用左子树的最大值或者右子树的最小值替代当前 r o o t root root。

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null)
            return null;
        if(root.val == key) {
            if(root.left == null) // 左空右为根
                return root.right;
            if(root.right == null) // 右空左为根
                return root.left;
            // 都不空取右最小（左）为根
            TreeNode t = root.right;
            while(t.left != null)
                t = t.left;
            t.left = root.left;
            return root.right;
        }
        else if(root.val < key) // 小了，往右找
            root.right = deleteNode(root.right, key);
        else // 大了，往左找
            root.left =deleteNode(root.left, key);
        return root;
    }
}

• 时间复杂度： O ( h ) O(h) O(h)，其中 h h h为树高
• 空间复杂度： O ( 1 ) O(1) O(1)，考虑递归的栈为 O ( n ) O(n) O(n)

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(root ==nullptr)
            return nullptr;
        if(root->val == key) {
            if(root->left == nullptr) // 左空右为根
                return root->right;
            if(root->right == nullptr) // 右空左为根
                return root->left;
            // 都不空取右最小（左）为根
            TreeNode* t = root->right;
            while(t->left != nullptr)
                t = t->left;
            t->left = root->left;
            return root->right;
        }
        else if(root->val < key) // 小了，往右找
            root->right = deleteNode(root->right, key);
        else // 大了，往左找
            root->left =deleteNode(root->left, key);
        return root;
    }
};

• 时间复杂度： O ( h ) O(h) O(h)，其中 h h h为树高
• 空间复杂度： O ( 1 ) O(1) O(1)，考虑递归的栈为 O ( n ) O(n) O(n)

报了个奇奇妙妙的错，什么蛇形命名、搞不懂……

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn delete_node(root: Option>>, key: i32) -> Option>> {
        if root.is_none() {
            return None
        }
        let mut node = root.unwrap().borrow();
        if node.val == key {
            if node.left.is_none() {
                return node.right.clone();
            }
            if node.right.is_none() {
                return node.left.clone();
            }
            let mut t = node.right.unwrap();
            while t.borrow().left.is_some() {
                t.borrow_mut() = t.borrow().left.clone();
            }
            t.borrow_mut().left = node.left;
            return node.right.clone();
        }
        else if node.val < key {
            node.right = Self::delete_node(node.right.clone(), key);
        }
        else {
            node.left = Self::delete_node(node.left.clone(), key);
        }
        return root;
    }
}

• 时间复杂度： O ( h ) O(h) O(h)，其中 h h h为树高
• 空间复杂度： O ( 1 ) O(1) O(1)，考虑递归的栈为 O ( n ) O(n) O(n)

简简单单递归模拟题、当然也可以改迭代写、偷懒就不搞了~