面试题8：二叉树的下一个节点

面试题8：二叉树的下一个节点

题意：给定一棵二叉树的其中一个节点，请找出中序遍历序列的下一个节点。树中节点还有一个指向父节点的指针。

算法：模拟

思路：1）如果该节点有右子树，右子树最左边的节点为其后继节点。
2）如果该节点没有右子树，那么向上寻找father节点，找到第一个是father左儿子的节点，则其father节点为其后继。

时间复杂度：O(h)

TreeNode* inorderSuccessor(TreeNode* p) {
    if(p -> right){
        p = p -> right;
        while(p -> left) p = p -> left;
        return p;
    }
    
    while(p -> father && p == p -> father -> right) p = p -> father;
    return p -> father;
}