Problem

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

Note: If the given node has no in-order successor in the tree, return null.

Solution

用中序遍歷的方式遍歷樹，這里這個節(jié)點的位置有幾種可能性：

1. 節(jié)點有右孩子：那么找到右孩子的最左邊的子孫。如果沒有子孫，那么就是右孩子本身。
2. 節(jié)點沒有右孩子：那么找到最close的上層父親，并且這個節(jié)點是這個父親左子樹的一員。

如果無法滿足上述情況，那么就沒有successor。另外，這里有幾個corner case，比如p == root，并且root沒有右孩子。比如，節(jié)點在node的右子樹中，如果node != root，返回p，如果node == root，返回null。

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
    TreeNode *find(TreeNode *root, TreeNode *p, TreeNode *treeRoot) {
        if (root == NULL) {
            return NULL;
        }
        TreeNode *left = find(root->left, p, treeRoot);
        if (left != p && left != NULL) {
            return left;
        } else if (p == left) {
            return root;
        }
        if (p == root) {
            TreeNode *node = p->right;
            TreeNode *preNode = NULL;
            while (node) {
                preNode = node;
                node = node->left;
            }
            if (preNode) {
                return preNode;
            } else {
                return root == treeRoot ? NULL : p;
            }
        }
        TreeNode *right = find(root->right, p, treeRoot);
    
        if (right != p && right != NULL) {
            return right;
        } else if (right == p) {
            if (root == treeRoot) {
                return NULL;
            } else {
                return p;
            }
        }
    
        return NULL;
    }

    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        return find(root, p, root);
    }
};