LeetCode 450 - Delete Node in a BST

作者 QIFAN 日期 2017-02-03
LeetCode 450 - Delete Node in a BST

原题链接: 450. Delete Node in a BST


题干

给定 BST 的根节点,实现删除操作。

思路

很基础的题。我算法系列的文章也会说到这个,大致就是分成没找到、没孩子、一个孩子、两个孩子的情况。

  • 没找到:返回 null
  • 没孩子:判断是父节点的左孩子还是右孩子,断连
  • 一个孩子:让这个孩子替代自己上位。
  • 两个孩子:找继承者(左边树的最大或者右边树的最小),继承者与原树断连上位,并接替左右孩子。

树的各种操作应该特别熟练,隔两周默一遍。

这里不要搞错的是,当继承者是待删节点的左孩子与当继承者不是待删节点的左孩子时继承者孩子的交接。

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) {
return null;
}
TreeNode curr = root;
TreeNode parent = null;
while (curr != null) {
if (curr.val == key) {
break;
}
parent = curr;
if (curr.val > key) {
curr = curr.left;
} else {
curr = curr.right;
}
}
if (curr == null) {
return root;
}
TreeNode successor;
// 没有孩子,直接删除,没有继承者
if (curr.left == null && curr.right == null) {
successor = null;
// 有一个孩子,继承者为孩子
} else if (curr.left == null || curr.right == null) {
if (curr.left == null) {
successor = curr.right;
curr.right = null;
} else {
successor = curr.left;
curr.left = null;
}
// 两个孩子
} else {
successor = getSuccessor(curr);
successor.left = curr.left;
successor.right = curr.right;
}
// 如果要删的是根节点,直接返回继承者
if (parent == null) {
return successor;
}
// 删的是左孩子
if (parent.val > curr.val) {
parent.left = successor;
// 删的是右孩子
} else {
parent.right = successor;
}
return root;
}
// 删除左边树的最大值并返回,即继承者
private TreeNode getSuccessor(TreeNode node) {
TreeNode parent = node;
node = node.left;
while (node.right != null) {
parent = node;
node = node.right;
}
if (parent.left == node) {
parent.left = node.left;
} else {
parent.right = node.left;
}
node.left = null;
return node;
}