/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode *father;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL), father(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* p) {
        //先判断目标节点的右孩子是否为空,如果不为空就继续往下找
        if(p->right != NULL){
            TreeNode *res = p->right;
            while(res != NULL && res->left != NULL)
                res = res->left;
            return res;
        }
        //如果为空就找父节点,若当前节点是父节点的左孩子就放回父节点,否则就继续往上找,直到父节点为空,就返回空;
        else{
            TreeNode *res = p->father, *ptr = p;
            while(res != NULL){
                if(res->left == ptr)
                    return res;
                else{
                    ptr = res;
                    res = res->father;
                }
            }
            return NULL;
        }
    }
};