Java教程

二叉树算法题(22)删除二叉搜索树中的节点

本文主要是介绍二叉树算法题(22)删除二叉搜索树中的节点,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录

删除二叉搜索树中的节点

描述

示例 1

示例 2

示例 3

提示

方法:递归


删除二叉搜索树中的节点

描述

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

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

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

示例 1

输入:root = [5,3,6,2,4,null,7], key = 3
输出:[5,4,6,2,null,null,7]
解释:给定需要删除的节点值是 3,所以我们首先找到 3 这个节点,然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。

示例 2

输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点

示例 3

输入: root = [], key = 0
输出: []

提示

  • 节点数的范围 [0, 10^4]
  • -10^5 \le Node.val \le 10^5
  • 节点值唯一
  • root 是合法的二叉搜索树
  • -10^5 \le key \le 10^5

进阶: 要求算法时间复杂度为 O(h),h 为树的高度。

方法:递归

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;//如果该节点左子树为空,那么就让右子树赋值给root
            else if (root.right==null) return root.left;//如果该节点右子树为空,就将左子树赋值给root
            else{//如果左右子树都不为空,则找该节点的后缀节点赋值给该节点
                TreeNode cur=root.right,pre=root;
                while (cur.left!=null) {
                    pre=cur;//更新pre的值
                    cur=cur.left;//查找右子树中最左的节点
                }
                if (pre==root){//如果该节点右边没有左子树了
                    pre.right=cur.right;//就将右边的右子树往上提
                }else pre.left=cur.right;//否则就将最左的节点右子树往上提,覆盖最左节点
                root.val=cur.val;//删除当前节点
            }
            return root;
        }else if (root.val<key) root.right=deleteNode(root.right,key);//在右子树查找节点
        else root.left=deleteNode(root.left,key);//在左子树查找节点
        return root;
    }
}

这篇关于二叉树算法题(22)删除二叉搜索树中的节点的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!