No big deal. 只是没有了root但是多了parent,肯定是拿这个parent做文章。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public Node inorderSuccessor(Node node) {
    // easest: direct right child; if no, to parent:
    // when parent.val smaller: cur is right child;
    // loop parent until parent.val > node.val
    if (node.right == null) {
        Node upper = node.parent;
        while (upper != null && upper.val < node.val) {
            upper = upper.parent;
        }
        return upper;
    // else: go to direct right child; find the smallest in right sub;
    // i.e. leftest child in this right sub tree
    } else {
        Node lower = node.right;
        while (lower.left != null) {
            lower = lower.left;
        }
        return lower;
    }
}