P92 二叉搜索树中删除节点

描述#

这个题目说的是，给你一棵二叉搜索树和一个数值，你要删除二叉搜索树上等于这个数值的节点，然后返回处理后的二叉搜索树。 注意，二叉搜索树的节点上没有重复数值，并且要求删除节点后返回的仍然是二叉搜索树。

比如说，给你的二叉搜索树是：
1

/ 

0   4
/ 

2   8
给你的数值为 4。删掉 4 这个节点后，可以返回：
1

/ 

0   2


8
也可以返回：
1

/ 

0   8
/
2
这两个都是有效的二叉搜索树，返回其中一个即可。

代码#

public class AlgoCasts {

  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }

  // Time: O(h), Space: O(h)
  public TreeNode deleteNodeInBST(TreeNode root, int val) {
    if (root == null) return null;
    if (val < root.val) {
      root.left = deleteNodeInBST(root.left, val);
    } else if (val > root.val) {
      root.right = deleteNodeInBST(root.right, val);
    } else {
      if (root.left == null) return root.right;
      else if (root.right == null) return root.left;

      TreeNode leftMax = root.left;
      while (leftMax.right != null) leftMax = leftMax.right;
      leftMax.right = root.right;
      root = root.left;
    }
    return root;
  }

}