二叉搜索树中删除节点

二叉搜索树中删除节点

问题

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

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

    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;
  }

}