LeetCode 450. 删除二叉搜索树中的节点
题目描述
思路分析
- 如果目标节点大于当前节点值，则去右子树中删除；
- 如果目标节点小于当前节点值，则去左子树中删除；
如果目标节点就是当前节点，分为以下三种情况：
a. 其无左子：其右子顶替其位置，删除了该节点；
b. 其无右子：其左子顶替其位置，删除了该节点；
c. 其左右子节点都有：其左子树转移到其右子树最左节点的左子树上，然后右子树顶替其位置，由此删除了该节点。
参考代码
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
func deleteNode(root *TreeNode, key int) *TreeNode {
// 如果根节点为空，返回空
if root == nil {
return nil
}
if key < root.Val {
// 如果 key 小于当前节点的值，递归到左子树
root.Left = deleteNode(root.Left, key)
} else if key > root.Val {
// 如果 key 大于当前节点的值，递归到右子树
root.Right = deleteNode(root.Right, key)
} else {
// 找到要删除的节点
if root.Left == nil && root.Right == nil {
// 叶子节点，直接删除
return nil
} else if root.Left == nil {
// 只有右子树
return root.Right
} else if root.Right == nil {
// 只有左子树
return root.Left
} else {
// 有两个子节点，找到右子树的最小节点
minNode := findMin(root.Right)
root.Val = minNode.Val
root.Right = deleteNode(root.Right, minNode.Val)
}
}
return root
}
// 寻找右子树的最小节点
func findMin(root *TreeNode) *TreeNode {
current := root
for current.Left != nil {
current = current.Left
}
return current
}
时间复杂度：O (h)，其中 h 是树的高度。
在最坏情况下，树可能退化为链表，时间复杂度为 O (n)。
空间复杂度：O (h)，用于递归调用栈的空间。
1
write your code here
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！