ChunNote
0%

leetCode-450:Delete Node in a BST

发表于 分类于

问题描述

给定一个搜索二叉树和一个数值，要求将树中该数值所在的节点删除。题目链接：点我

样例输入输出

输入：root = [5,3,6,2,4,null,7], key = 3

输出：[5,4,6,2,null,null,7]

解释：树的形状如下

删除节点树图

注：删除后的树形状也可以是以下的结果，两种结果返回任何一种都可以

输入：root = [3], key = 3

输出：[]

问题解法

按照搜索二叉树特性，先找到要删除的节点，然后将该节点的左子树的最右节点替换到要删除的节点即可。大体思路比较直观，只是在求解过程中需要考虑多种情况，如果节点是否为空。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        TreeNode dummy = new TreeNode(Integer.MAX_VALUE, root, null);
        TreeNode current = dummy;
        TreeNode targetNode = null;
        boolean isLeft = false;
        while (current != null) {
            if (current.val > key) {
                if (current.left != null && current.left.val == key) {
                    isLeft = true;
                    targetNode = current.left;
                    break;
                }

                current = current.left;
            } else if (current.val < key) {
                if (current.right != null && current.right.val == key) {
                    isLeft = false;
                    targetNode = current.right;
                    break;
                }

                current = current.right;
            } else {
                break;
            }
        }

        // key 不存在树中，直接返回
        if (targetNode == null) {
            return dummy.left;
        }

        if (targetNode.left == null) {
            if (isLeft) {
                current.left = targetNode.right;
            } else {
                current.right = targetNode.right;
            }
        } else if (targetNode.right == null) {
            if (isLeft) {
                current.left = targetNode.left;
            } else {
                current.right = targetNode.left;
            }
        } else {
            TreeNode temp = targetNode.left;
            TreeNode parent = targetNode;
            while (temp.right != null) {
                parent = temp;
                temp = temp.right;
            }

            // 左节点不存在右节点的情况
            if (parent != targetNode) {
                parent.right = temp.left;
                temp.left = targetNode.left;
            }
            
            temp.right = targetNode.right;
            if (isLeft) {
                current.left = temp;
            } else {
                current.right = temp;
            }
        }

        return dummy.left;
    }
}