题目描述

二叉树的下一个节点

样例

2,1,3; 1 -> 3

算法1

if p->right, go to left most of right subtree, else go upward till the first parent that is on the left hand side

时间复杂度

O(N)

参考文献

C++ 代码

/**
 * 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)
        {
            p = p->right;
            while (p->left)
                p = p->left;
        }
        else
        {
            TreeNode* next = p;
            p = p->father;
            while (p && p->right == next)
            {
                next = p;
                p = p->father;
            }
        }

        return p;
    }
};