【题目描述】

AcWing 19. 二叉树的下一个节点

【思路】

情况1：该节点存在右子树，那么其右孩子的最左边即是该节点的后继。如F节点的后继是H。
情况2：该节点（如D）不存在右子树，且该节点（B）是其父节点（D）的右孩子，则向上回溯其父节点，直到找到第一个其father的左孩子是它自己（C）的节点。则这个节点的父节点（F）是要找的那个节点（B）的后继。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode father;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode inorderSuccessor(TreeNode p) {
        if(p.right != null){
            p = p.right;
            while( p.left != null) p = p.left;
            return p;
        }
        while( p.father != null && p == p.father.right) p = p.father;
        //其他情况则直接返回p.father  如B
        return p.father;


    }
}