Skip to content

Latest commit

 

History

History
808 lines (709 loc) · 26.6 KB

0450.删除二叉搜索树中的节点.md

File metadata and controls

808 lines (709 loc) · 26.6 KB
Raw

参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们受益！

二叉搜索树删除节点就涉及到结构调整了

450.删除二叉搜索树中的节点

力扣题目链接

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点； 如果找到了，删除它。 说明： 要求算法时间复杂度为 $O(h)$，h 为树的高度。

示例:

450.删除二叉搜索树中的节点

算法公开课

《代码随想录》算法视频公开课：调整二叉树的结构最难！| LeetCode：450.删除二叉搜索树中的节点，相信结合视频再看本篇题解，更有助于大家对本题的理解。

思路

搜索树的节点删除要比节点增加复杂的多，有很多情况需要考虑，做好心理准备。

递归

递归三部曲：

  • 确定递归函数参数以及返回值

说到递归函数的返回值，在二叉树：搜索树中的插入操作中通过递归返回值来加入新节点， 这里也可以通过递归返回值删除节点。

代码如下：

TreeNode* deleteNode(TreeNode* root, int key)
  • 确定终止条件

遇到空返回，其实这也说明没找到删除的节点，遍历到空节点直接返回了

if (root == nullptr) return root;
  • 确定单层递归的逻辑

这里就把二叉搜索树中删除节点遇到的情况都搞清楚。

有以下五种情况：

  • 第一种情况：没找到删除的节点，遍历到空节点直接返回了
  • 找到删除的节点
    • 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
    • 第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
    • 第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
    • 第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。

第五种情况有点难以理解，看下面动画：

450.删除二叉搜索树中的节点

动画中的二叉搜索树中，删除元素7， 那么删除节点（元素7）的左孩子就是5，删除节点（元素7）的右子树的最左面节点是元素8。

将删除节点（元素7）的左孩子放到删除节点（元素7）的右子树的最左面节点（元素8）的左孩子上，就是把5为根节点的子树移到了8的左孩子的位置。

要删除的节点（元素7）的右孩子（元素9）为新的根节点。.

这样就完成删除元素7的逻辑，最好动手画一个图，尝试删除一个节点试试。

代码如下：

if (root->val == key) {
    // 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
    // 第三种情况：其左孩子为空，右孩子不为空，删除节点，右孩子补位 ，返回右孩子为根节点
    if (root->left == nullptr) return root->right;
    // 第四种情况：其右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
    else if (root->right == nullptr) return root->left;
    // 第五种情况：左右孩子节点都不为空，则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置
    // 并返回删除节点右孩子为新的根节点。
    else {
        TreeNode* cur = root->right; // 找右子树最左面的节点
        while(cur->left != nullptr) {
            cur = cur->left;
        }
        cur->left = root->left; // 把要删除的节点（root）左子树放在cur的左孩子的位置
        TreeNode* tmp = root;   // 把root节点保存一下，下面来删除
        root = root->right;     // 返回旧root的右孩子作为新root
        delete tmp;             // 释放节点内存（这里不写也可以，但C++最好手动释放一下吧）
        return root;
    }
}

这里相当于把新的节点返回给上一层，上一层就要用 root->left 或者 root->right接住，代码如下：

if (root->val > key) root->left = deleteNode(root->left, key);
if (root->val < key) root->right = deleteNode(root->right, key);
return root;

整体代码如下：（注释中：情况1，2，3，4，5和上面分析严格对应）

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == nullptr) return root; // 第一种情况：没找到删除的节点，遍历到空节点直接返回了
        if (root->val == key) {
            // 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
            if (root->left == nullptr && root->right == nullptr) {
                ///! 内存释放
                delete root;
                return nullptr;
            }
            // 第三种情况：其左孩子为空，右孩子不为空，删除节点，右孩子补位 ，返回右孩子为根节点
            else if (root->left == nullptr) {
                auto retNode = root->right;
                ///! 内存释放
                delete root;
                return retNode;
            }
            // 第四种情况：其右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
            else if (root->right == nullptr) {
                auto retNode = root->left;
                ///! 内存释放
                delete root;
                return retNode;
            }
            // 第五种情况：左右孩子节点都不为空，则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置
            // 并返回删除节点右孩子为新的根节点。
            else {
                TreeNode* cur = root->right; // 找右子树最左面的节点
                while(cur->left != nullptr) {
                    cur = cur->left;
                }
                cur->left = root->left; // 把要删除的节点（root）左子树放在cur的左孩子的位置
                TreeNode* tmp = root;   // 把root节点保存一下，下面来删除
                root = root->right;     // 返回旧root的右孩子作为新root
                delete tmp;             // 释放节点内存（这里不写也可以，但C++最好手动释放一下吧）
                return root;
            }
        }
        if (root->val > key) root->left = deleteNode(root->left, key);
        if (root->val < key) root->right = deleteNode(root->right, key);
        return root;
    }
};

普通二叉树的删除方式

这里我在介绍一种通用的删除，普通二叉树的删除方式（没有使用搜索树的特性，遍历整棵树），用交换值的操作来删除目标节点。

代码中目标节点（要删除的节点）被操作了两次：

  • 第一次是和目标节点的右子树最左面节点交换。
  • 第二次直接被NULL覆盖了。

思路有点绕，感兴趣的同学可以画图自己理解一下。

代码如下：（关键部分已经注释）

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == nullptr) return root;
        if (root->val == key) {
            if (root->right == nullptr) { // 这里第二次操作目标值：最终删除的作用
                return root->left;
            }
            TreeNode *cur = root->right;
            while (cur->left) {
                cur = cur->left;
            }
            swap(root->val, cur->val); // 这里第一次操作目标值：交换目标值其右子树最左面节点。
        }
        root->left = deleteNode(root->left, key);
        root->right = deleteNode(root->right, key);
        return root;
    }
};

这个代码是简短一些，思路也巧妙，但是不太好想，实操性不强，推荐第一种写法！

迭代法

删除节点的迭代法还是复杂一些的，但其本质我在递归法里都介绍了，最关键就是删除节点的操作（动画模拟的过程）

代码如下：

class Solution {
private:
    // 将目标节点（删除节点）的左子树放到 目标节点的右子树的最左面节点的左孩子位置上
    // 并返回目标节点右孩子为新的根节点
    // 是动画里模拟的过程
    TreeNode* deleteOneNode(TreeNode* target) {
        if (target == nullptr) return target;
        if (target->right == nullptr) return target->left;
        TreeNode* cur = target->right;
        while (cur->left) {
            cur = cur->left;
        }
        cur->left = target->left;
        return target->right;
    }
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == nullptr) return root;
        TreeNode* cur = root;
        TreeNode* pre = nullptr; // 记录cur的父节点，用来删除cur
        while (cur) {
            if (cur->val == key) break;
            pre = cur;
            if (cur->val > key) cur = cur->left;
            else cur = cur->right;
        }
        if (pre == nullptr) { // 如果搜索树只有头结点
            return deleteOneNode(cur);
        }
        // pre 要知道是删左孩子还是右孩子
        if (pre->left && pre->left->val == key) {
            pre->left = deleteOneNode(cur);
        }
        if (pre->right && pre->right->val == key) {
            pre->right = deleteOneNode(cur);
        }
        return root;
    }
};

总结

读完本篇，大家会发现二叉搜索树删除节点比增加节点复杂的多。

因为二叉搜索树添加节点只需要在叶子上添加就可以的，不涉及到结构的调整，而删除节点操作涉及到结构的调整。

这里我们依然使用递归函数的返回值来完成把节点从二叉树中移除的操作。

这里最关键的逻辑就是第五种情况（删除一个左右孩子都不为空的节点），这种情况一定要想清楚。

而且就算想清楚了，对应的代码也未必可以写出来，所以这道题目既考察思维逻辑，也考察代码能力。

递归中我给出了两种写法，推荐大家学会第一种（利用搜索树的特性）就可以了，第二种递归写法其实是比较绕的。

最后我也给出了相应的迭代法，就是模拟递归法中的逻辑来删除节点，但需要一个pre记录cur的父节点，方便做删除操作。

迭代法其实不太容易写出来，所以如果是初学者的话，彻底掌握第一种递归写法就够了。

其他语言版本

Java

// 解法1(最好理解的版本)
class Solution {
  public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) return root;
    if (root.val == key) {
      if (root.left == null) {
        return root.right;
      } else if (root.right == null) {
        return root.left;
      } else {
        TreeNode cur = root.right;
        while (cur.left != null) {
          cur = cur.left;
        }
        cur.left = root.left;
        root = root.right;
        return root;
      }
    }
    if (root.val > key) root.left = deleteNode(root.left, key);
    if (root.val < key) root.right = deleteNode(root.right, key);
    return root;
  }
}
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        root = delete(root,key);
        return root;
    }

    private TreeNode delete(TreeNode root, int key) {
        if (root == null) return null;

        if (root.val > key) {
            root.left = delete(root.left,key);
        } else if (root.val < key) {
            root.right = delete(root.right,key);
        } else {
            if (root.left == null) return root.right;
            if (root.right == null) return root.left;
            TreeNode tmp = root.right;
            while (tmp.left != null) {
                tmp = tmp.left;
            }
            root.val = tmp.val;
            root.right = delete(root.right,tmp.val);
        }
        return root;
    }
}

递归法

class Solution {
  public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null){
      return null;
    }
    //寻找对应的对应的前面的节点，以及他的前一个节点
    TreeNode cur = root;
    TreeNode pre = null;
    while (cur != null){
      if (cur.val < key){
        pre = cur;
        cur = cur.right;
      } else if (cur.val > key) {
        pre = cur;
        cur = cur.left;
      }else {
        break;
      }
    }
    if (pre == null){
      return deleteOneNode(cur);
    }
    if (pre.left !=null && pre.left.val == key){
      pre.left = deleteOneNode(cur);
    }
    if (pre.right !=null && pre.right.val == key){
      pre.right = deleteOneNode(cur);
    }
    return root;
  }

  public TreeNode deleteOneNode(TreeNode node){
    if (node == null){
      return null;
    }
    if (node.right == null){
      return node.left;
    }
    TreeNode cur = node.right;
    while (cur.left !=null){
      cur = cur.left;
    }
    cur.left = node.left;
    return node.right;
  }
}

Python

递归法（版本一）

class Solution:
    def deleteNode(self, root, key):
        if root is None:
            return root
        if root.val == key:
            if root.left is None and root.right is None:
                return None
            elif root.left is None:
                return root.right
            elif root.right is None:
                return root.left
            else:
                cur = root.right
                while cur.left is not None:
                    cur = cur.left
                cur.left = root.left
                return root.right
        if root.val > key:
            root.left = self.deleteNode(root.left, key)
        if root.val < key:
            root.right = self.deleteNode(root.right, key)
        return root

递归法（版本二）

class Solution:
    def deleteNode(self, root, key):
        if root is None:  # 如果根节点为空，直接返回
            return root
        if root.val == key:  # 找到要删除的节点
            if root.right is None:  # 如果右子树为空，直接返回左子树作为新的根节点
                return root.left
            cur = root.right
            while cur.left:  # 找到右子树中的最左节点
                cur = cur.left
            root.val, cur.val = cur.val, root.val  # 将要删除的节点值与最左节点值交换
        root.left = self.deleteNode(root.left, key)  # 在左子树中递归删除目标节点
        root.right = self.deleteNode(root.right, key)  # 在右子树中递归删除目标节点
        return root

迭代法

class Solution:
    def deleteOneNode(self, target: TreeNode) -> TreeNode:
        """
        将目标节点（删除节点）的左子树放到目标节点的右子树的最左面节点的左孩子位置上
        并返回目标节点右孩子为新的根节点
        是动画里模拟的过程
        """
        if target is None:
            return target
        if target.right is None:
            return target.left
        cur = target.right
        while cur.left:
            cur = cur.left
        cur.left = target.left
        return target.right

    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
        if root is None:
            return root
        cur = root
        pre = None  # 记录cur的父节点，用来删除cur
        while cur:
            if cur.val == key:
                break
            pre = cur
            if cur.val > key:
                cur = cur.left
            else:
                cur = cur.right
        if pre is None:  # 如果搜索树只有头结点
            return self.deleteOneNode(cur)
        # pre 要知道是删左孩子还是右孩子
        if pre.left and pre.left.val == key:
            pre.left = self.deleteOneNode(cur)
        if pre.right and pre.right.val == key:
            pre.right = self.deleteOneNode(cur)
        return root

Go

// 递归版本
func deleteNode(root *TreeNode, key int) *TreeNode {
    if root == nil {
        return nil
    }
    if key < root.Val {
        root.Left = deleteNode(root.Left, key)
        return root
    }
    if key > root.Val {
        root.Right = deleteNode(root.Right, key)
        return root
    }
    if root.Right == nil {
        return root.Left
    }
    if root.Left == nil{
        return root.Right
    }
    minnode := root.Right
    for minnode.Left != nil {
        minnode = minnode.Left
    }
    root.Val = minnode.Val
    root.Right = deleteNode1(root.Right)
    return root
}

func deleteNode1(root *TreeNode)*TreeNode {
    if root.Left == nil {
        pRight := root.Right
        root.Right = nil
        return pRight
    }
    root.Left = deleteNode1(root.Left)
    return root
}
// 迭代版本
func deleteOneNode(target *TreeNode) *TreeNode {
	if target == nil {
		return target
	}
	if target.Right == nil {
		return target.Left
	}
	cur := target.Right
	for cur.Left != nil {
		cur = cur.Left
	}
	cur.Left = target.Left
	return target.Right
}
func deleteNode(root *TreeNode, key int) *TreeNode {
	// 特殊情况处理
	if root == nil {
		return root
	}
	cur := root
	var pre *TreeNode
	for cur != nil {
		if cur.Val == key {
			break
		}
		pre = cur
		if cur.Val > key {
			cur = cur.Left
		} else {
			cur = cur.Right
		}
	}
	if pre == nil {
		return deleteOneNode(cur)
	}
	// pre 要知道是删除左孩子还有右孩子
	if pre.Left != nil && pre.Left.Val == key {
		pre.Left = deleteOneNode(cur)
	}
	if pre.Right != nil && pre.Right.Val == key {
		pre.Right = deleteOneNode(cur)
	}
	return root
}

JavaScript

递归

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} key
 * @return {TreeNode}
 */
var deleteNode = function(root, key) {
    if (!root) return null;
    if (key > root.val) {
        root.right = deleteNode(root.right, key);
        return root;
    } else if (key < root.val) {
        root.left = deleteNode(root.left, key);
        return root;
    } else {
        // 场景1: 该节点是叶节点
        if (!root.left && !root.right) {
            return null
        }
        // 场景2: 有一个孩子节点不存在
        if (root.left && !root.right) {
            return root.left;
        } else if (root.right && !root.left) {
            return root.right;
        }
        // 场景3: 左右节点都存在
        const rightNode = root.right;
        // 获取最小值节点
        const minNode = getMinNode(rightNode);
        // 将待删除节点的值替换为最小值节点值
        root.val = minNode.val;
        // 删除最小值节点
        root.right = deleteNode(root.right, minNode.val);
        return root;
    }
};
function getMinNode(root) {
    while (root.left) {
        root = root.left;
    }
    return root;
}

迭代

var deleteNode = function (root, key) {
    const deleteOneNode = target => {
        if (!target) return target
        if (!target.right) return target.left
        let cur = target.right
        while (cur.left) {
            cur = cur.left
        }
        cur.left = target.left
        return target.right
    }

    if (!root) return root
    let cur = root
    let pre = null
    while (cur) {
        if (cur.val === key) break
        pre = cur
        cur.val > key ? cur = cur.left : cur = cur.right
    }
    if (!pre) {
        return deleteOneNode(cur)
    }
    if (pre.left && pre.left.val === key) {
        pre.left = deleteOneNode(cur)
    }
    if (pre.right && pre.right.val === key) {
        pre.right = deleteOneNode(cur)
    }
    return root
}

TypeScript

递归法：

function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
    if (root === null) return null;
    if (root.val === key) {
        if (root.left === null && root.right === null) return null;
        if (root.left === null) return root.right;
        if (root.right === null) return root.left;
        let curNode: TreeNode = root.right;
        while (curNode.left !== null) {
            curNode = curNode.left;
        }
        curNode.left = root.left;
        return root.right;
    }
    if (root.val > key) root.left = deleteNode(root.left, key);
    if (root.val < key) root.right = deleteNode(root.right, key);
    return root;
};

迭代法：

function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
    function removeTargetNode(root: TreeNode): TreeNode | null {
        if (root.left === null && root.right === null) return null;
        if (root.right === null) return root.left;
        if (root.left === null) return root.right;
        let curNode: TreeNode | null = root.right;
        while (curNode.left !== null) {
            curNode = curNode.left;
        }
        curNode.left = root.left;
        return root.right;
    }
    let preNode: TreeNode | null = null,
        curNode: TreeNode | null = root;
    while (curNode !== null) {
        if (curNode.val === key) break;
        preNode = curNode;
        if (curNode.val > key) {
            curNode = curNode.left;
        } else {
            curNode = curNode.right;
        }
    }
    if (curNode === null) return root;
    if (preNode === null) {
        // 删除头节点
        return removeTargetNode(curNode);
    }
    if (preNode.val > key) {
        preNode.left = removeTargetNode(curNode);
    } else {
        preNode.right = removeTargetNode(curNode);
    }
    return root;
};

Scala

object Solution {
  def deleteNode(root: TreeNode, key: Int): TreeNode = {
    if (root == null) return root // 第一种情况，没找到删除的节点，遍历到空节点直接返回
    if (root.value == key) {
      // 第二种情况: 左右孩子都为空，直接删除节点，返回null
      if (root.left == null && root.right == null) return null
      // 第三种情况: 左孩子为空，右孩子不为空，右孩子补位
      else if (root.left == null && root.right != null) return root.right
      // 第四种情况: 左孩子不为空，右孩子为空，左孩子补位
      else if (root.left != null && root.right == null) return root.left
      // 第五种情况: 左右孩子都不为空，将删除节点的左子树头节点(左孩子)放到
      //           右子树的最左边节点的左孩子上，返回删除节点的右孩子
      else {
        var tmp = root.right
        while (tmp.left != null) tmp = tmp.left
        tmp.left = root.left
        return root.right
      }
    }
    if (root.value > key) root.left = deleteNode(root.left, key)
    if (root.value < key) root.right = deleteNode(root.right, key)

    root // 返回根节点，return关键字可以省略
  }
}

Rust

impl Solution {
    pub fn delete_node(
        root: Option<Rc<RefCell<TreeNode>>>,
        key: i32,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        root.as_ref()?;

        let mut node = root.as_ref().unwrap().borrow_mut();
        match node.val.cmp(&key) {
            std::cmp::Ordering::Less => node.right = Self::delete_node(node.right.clone(), key),
            std::cmp::Ordering::Equal => match (node.left.clone(), node.right.clone()) {
                (None, None) => return None,
                (None, Some(r)) => return Some(r),
                (Some(l), None) => return Some(l),
                (Some(l), Some(r)) => {
                    let mut cur = Some(r.clone());
                    while let Some(n) = cur.clone().unwrap().borrow().left.clone() {
                        cur = Some(n);
                    }
                    cur.unwrap().borrow_mut().left = Some(l);
                    return Some(r);
                }
            },
            std::cmp::Ordering::Greater => node.left = Self::delete_node(node.left.clone(), key),
        }
        drop(node);
        root
    }
}

C#

递归法：

    public TreeNode DeleteNode(TreeNode root, int key) {
        // 第一种情况：没找到删除的节点，遍历到空节点直接返回了
        if (root == null) return null;
        if(key == root.val) {
            //第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
            if(root.left == null && root.right == null) return null;
            //第三种情况：其左孩子为空，右孩子不为空，删除节点，右孩子补位 ，返回右孩子为根节点
            if (root.left == null && root.right != null) return root.right;
            //第四种情况：其右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
            if (root.left != null && root.right == null) return root.left;
            //第五种情况：左右孩子节点都不为空，则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置
            // 并返回删除节点右孩子为新的根节点。
            if(root.left != null && root.right != null) {
                TreeNode leftNode = root.right;	// 找右子树最左面的节点
                while(leftNode.left != null)
                    leftNode = leftNode.left;
                leftNode.left = root.left;	// 把要删除的节点（root）左子树放在leftNode的左孩子的位置
                return root.right;		// 返回旧root的右孩子作为新root
            }
        }

        if(root.val > key) root.left = DeleteNode(root.left, key);
        if(root.val < key) root.right = DeleteNode(root.right, key);

        return root;
    }