思路

本题所给定的节点共有2种情况

1.给定节点存在右子树，则只需要对右子树进行中序遍历，找到最左边的节点返回即可；

2.给定节点无右子树，且该节点是其父节点的左节点，直接返回父节点即可；
否则，该节点是其父节点的右节点，这种情况说明给定节点所在的左子树已经遍历完了，重点是找到该左子树的父节点。所以我们需要不断向上找，直到找到一个节点，该节点是其父节点的左节点，然后返回其父节点即可。

/**
 * 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) {
        //p有右子树
        if(p->right)
        {
            p=p->right;
            while(p->left) p=p->left;
            return p;
        }
        //p没有右子树
        while(p->father&&p==p->father->right)
            p=p->father;

        return p->father;
    }             
};