给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。
方法一:递归
public TreeNode deleteNode(TreeNode root, int key){
if(root == null) return null;
if(root.val < key) root.right = deleteNode(root.right, key);
if(root.val > key) root.left = deleteNode(root.left, key);
if(root.val == key) {
if(root.left == null && root.right == null) return null;
if(root.left == null) return root.right;
if(root.right == null) return root.left;
TreeNode successor = root.right;
// 找到右子树中最小的节点
while(successor.left != null) successor = successor.left;
// 删除右子树中最小的节点,并做好后续工作
root.right = deleteNode(root.right, successor.val);
// 取出root右子树中最小的节点,作为根节点
successor.left = root.left;
successor.right = root.right;
return successor;
}
return root;
}
美啊!这代码,整齐的美