LeetCode Delete Node in a BST Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST. Basically, the deletion can be divided into two stages:

1. Search for a node to remove.
2. If the node is found, delete the node.

Note: Time complexity should be O(height of tree). Example:

root = [5,3,6,2,4,null,7]
key = 3
    5
   / \
  3   6
 / \   \
2   4   7
Given key to delete is 3. So we find the node with value 3 and delete it.
One valid answer is [5,4,6,2,null,null,7], shown in the following BST.
    5
   / \
  4   6
 /     \
2       7
Another valid answer is [5,2,6,null,4,null,7].
    5
   / \
  2   6
   \   \
    4   7

---

从二叉搜索树中删除一个节点，并返回一个新的二叉搜索树；如果该节点不存在，则返回原二叉搜索树。 因为是BST，所以很容易找到等于value的节点，问题的关键是怎样删除这个节点，并且保持二叉搜索树的特性：左孩子<根节点<右孩子。 如果要删除的节点的左子树为空，则删除该节点，返回该节点的右子树即可；类似的，如果要删除的节点的右子树为空，则删除该节点，返回该节点的左子树。 难点就是当该节点的左子树和右子树都不为空时，该怎么处理。如下图，假设我们找到了root的值等于key，则需要删除root节点，并调整其子树使满足BST的性质。

       root
      /    \
   left  right
  /   \  /   \
 x    l r     y

具体有两种方案，题目中也举了例子，即可以把left放到root的位置，或者把right放到root的位置。 现在假设要把left放到root的位置，则需要处理left的右子树l。l肯定要被切下来，又l比left大，所以l应该接在right子树，具体位置是接在right子树的最小节点上，即right的最左下端的叶子节点r。也就是变成下面这样：

    left            right
    /  \            /   \
   x               r     y
                  /
                 l 

最后把right子树接在left右子树即可：

            left
            /  \
           x    right
                /   \
               r     y
              /
             l  

知道了调整的思路，代码就好写了： [cpp] class Solution { private: TreeNode* justify(TreeNode *root) { if (root->left == NULL || root->right == NULL)return root->left == NULL ? root->right : root->left; TreeNode *left = root->left, *right = root->right; TreeNode *l = left->right, *r = right; while (r->left) r = r->left; r->left = l; left->right = right; return left; } public: TreeNode* deleteNode(TreeNode* root, int key) { TreeNode *dummy = new TreeNode(-1), *pre = dummy, *child = root; dummy->right = root; while (child != NULL && child->val != key) { pre = child; if (key < child->val) child = child->left; else child = child->right; } if (child == NULL)return dummy->right; if (pre->left == child)pre->left = justify(child); else pre->right = justify(child); return dummy->right; } }; [/cpp] 本代码提交AC，用时33MS。 如果要把right放到root的位置，思路是类似的，需要把right的左子树切下来接到left最右下端的叶子节点上。 参考：https://segmentfault.com/a/1190000005032508]]>