标签搜索

目 录CONTENT

文章目录

【算法模板】二叉树节点删除

陈铭
2022-06-02 / 0 评论 / 2 点赞 / 209 阅读 / 491 字 / 正在检测是否收录...

例题:删除二叉搜索树中的节点

力扣面试题 450题为例:

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

一般来说,删除节点可分为两个步骤:

首先找到需要删除的节点;
如果找到了,删除它。

// 深搜遍历本身不是难事,重要的是如何保持节点删除后,顶层树和子树的拼接
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        if (root.val > key) {
            root.left = deleteNode(root.left, key);
            return root;
        }
        if (root.val < key) {
            root.right = deleteNode(root.right, key);
            return root;
        }
		// 找到删除的节点
        if (root.val == key) {
            if (root.left == null && root.right == null) {
                return null;
            }
            if (root.right == null) {
                return root.left;
            }
            if (root.left == null) {
                return root.right;
            }
			// 套路:删除的节点都有左右子树,那么就找到右子树的最小节点
			// 这个最小节点可以建立一个新的子树:即它的左子树是删除节点的左子树(最小节点正好是删除节点右子树中,大于删除节点左子树的最小值);同时它的右子树可以是“去除了当前这个最小节点的删除节点右子树”(去除后的删除节点右子树所有节点值都大于最小节点)。
			// 那么最小节点可以替代删除节点,拼接回顶层树。
			
			// 1. 找到最小节点
            TreeNode successor = root.right;
            while (successor.left != null) {
                successor = successor.left;
            }
			
			// 2. 去除了当前这个最小节点的删除节点右子树
            root.right = deleteNode(root.right, successor.val);
			
			// 3. 建立一个新的子树,拼接回顶层树
            successor.right = root.right;
            successor.left = root.left;
            return successor;
        }
        return root;
    }
}
2

评论区