510 Inorder Successor in BST II

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

The successor of a nodepis the node with the smallest key greater thanp.val.

You will have direct access to the node but not to the root of the tree. Each node will have a reference to its parent node.

Example 1:

Input: 
root = {"$id":"1","left":{"$id":"2","left":null,"parent":{"$ref":"1"},"right":null,"val":1},"parent":null,"right":{"$id":"3","left":null,"parent":{"$ref":"1"},"right":null,"val":3},"val":2}
p = 1

Output: 2
Explanation: 1's in-order successor node is 2. Note that both p and the return value is of Node type.

Example 2:

Input: 
root = 
{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":{"$id":"4","left":null,"parent":{"$ref":"3"},"right":null,"val":1},"parent":{"$ref":"2"},"right":null,"val":2},"parent":{"$ref":"1"},"right":{"$id":"5","left":null,"parent":{"$ref":"2"},"right":null,"val":4},"val":3},"parent":null,"right":{"$id":"6","left":null,"parent":{"$ref":"1"},"right":null,"val":6},"val":5}
p = 6

Output: null
Explanation: 
There is no in-order successor of the current node, so the answer is null.

Example 3:

Input: 
root = {"$id":"1","left":{"$id":"2","left":{"$id":"3","left":{"$id":"4","left":null,"parent":{"$ref":"3"},"right":null,"val":2},"parent":{"$ref":"2"},"right":{"$id":"5","left":null,"parent":{"$ref":"3"},"right":null,"val":4},"val":3},"parent":{"$ref":"1"},"right":{"$id":"6","left":null,"parent":{"$ref":"2"},"right":{"$id":"7","left":{"$id":"8","left":null,"parent":{"$ref":"7"},"right":null,"val":9},"parent":{"$ref":"6"},"right":null,"val":13},"val":7},"val":6},"parent":null,"right":{"$id":"9","left":{"$id":"10","left":null,"parent":{"$ref":"9"},"right":null,"val":17},"parent":{"$ref":"1"},"right":{"$id":"11","left":null,"parent":{"$ref":"9"},"right":null,"val":20},"val":18},"val":15}
p = 15
Output: 17

Example 4:

Input: 
root = {"$id":"1","left":{"$id":"2","left":{"$id":"3","left":{"$id":"4","left":null,"parent":{"$ref":"3"},"right":null,"val":2},"parent":{"$ref":"2"},"right":{"$id":"5","left":null,"parent":{"$ref":"3"},"right":null,"val":4},"val":3},"parent":{"$ref":"1"},"right":{"$id":"6","left":null,"parent":{"$ref":"2"},"right":{"$id":"7","left":{"$id":"8","left":null,"parent":{"$ref":"7"},"right":null,"val":9},"parent":{"$ref":"6"},"right":null,"val":13},"val":7},"val":6},"parent":null,"right":{"$id":"9","left":{"$id":"10","left":null,"parent":{"$ref":"9"},"right":null,"val":17},"parent":{"$ref":"1"},"right":{"$id":"11","left":null,"parent":{"$ref":"9"},"right":null,"val":20},"val":18},"val":15}
p = 13

Output: 15

Note:

1. If the given node has no in-order successor in the tree, returnnull.

2. It's guaranteed that the values of the tree are unique.

3. Remember that we are using theNodetype instead ofTreeNodetype so their string representation are different.

Follow up:

Could you solve it without looking up any of the node's values?

这题edge case比较多，不过也就是上面那几种。要注意一直找parent直到不是parent的左孩子为止。

public Node inorderSuccessor(Node x) {
    if (x == null) {
        return null;
    }

    if (x.right == null) {
        // 如果是根，或者根的右子树，要这样判断，一直往上找，找到是左子树为止         
        while (x.parent != null && x.parent.right == x) {
            x = x.parent;
        }                    
        return x.parent;              
    } else {
        // 如果有右子树的话，容易找，就是最左子树
        Node cur = x.right;
        while (cur.left != null) {
            cur = cur.left;                
        }

        return cur;
    }
}