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

试题链接：19. 二叉树的下一个节点 - AcWing题库

方法一：分类讨论

• 思路：如果存在右子树，则答案为右子树最左侧的节点；如果不存在右子树，且当前节点是其父节点的左儿子，则答案为父节点；如果不存在右子树，且当前节点是其父节点的右儿子，则需要不断取父节点，直到取到当前节点为父节点的左儿子时，答案为其父节点。
• 时间复杂度：O(n)
• 空间复杂度：O(1)

class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* p) {
        if (!p) return nullptr;
        
        if (p->right) {
            p = p->right;
            while (p->left) p = p->left;
            return p;
        }
        
        if (!p->father) return nullptr;
        
        if (p->father->left == p) {
            return p->father;
        }
        
        while (p->father && p->father->right == p) {
            p = p->father;
        }
        
        return p->father;
    }
};