首页 > 其他分享 >代码随想录Day38

代码随想录Day38

时间:2022-12-08 23:55:05浏览次数:53  
标签:right Day38 代码 随想录 key null root 节点 left

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

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

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

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

示例:

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

 

递归三部曲:

1.确定返回值和参数:

传入根节点和需要删除的数值,返回值为根节点的引用。

2.终止条件:

空值直接返回,没有找到需要删除的数值。

3.单层递归逻辑

这里才是难点,删除和插入不同,插入有空即插入,删除需要考虑的情况很多。

1)没有找到删除节点,直接返回

2)左右孩子节点为空,直接删除节点,返回null

3)删除节点左孩子为null,右孩子不空,删除节点,右孩子补位到根节点

4)删除节点的右孩子为null,左孩子不空,删除节点,左孩子补位到根节点

5)左右孩子节点都不为空,则将删除节点的左子树头结点(左孩子)放到删除节点的右子树的最左面节点的左孩子上,返回删除节点右孩子为新的根节点。

 

代码:

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;
    }
}
// 解法2
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;
  }
}

 

标签:right,Day38,代码,随想录,key,null,root,节点,left
From: https://www.cnblogs.com/dwj-ngu/p/16967770.html

相关文章