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

题目描述:给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。一般来说,删除节点可分为两个步骤:

  • 首先找到需要删除的节点;

  • 如果找到了,删除它。

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

代码实现

递归实现

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
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;
}
if (root.right == null) {
return root.left;
}
TreeNode minNode = getMinNode(root.right);
root.val = minNode.val;
root.right = deleteNode(root.right, minNode.val);
return root;
} else if (root.val > key) {
root.left = deleteNode(root.left, key);
} else if (root.val < key) {
root.right = deleteNode(root.right, key);
}
return root;
}

private TreeNode getMinNode(TreeNode root) {
while (root.left != null) {
root = root.left;
}
return root;
}
}