二叉树的下一个结点（ZJ57）

题目简述

        给定二叉树的某个节点pNode，求出该节点在中序遍历中的下一个节点。

算法一:

时间复杂度：O(N) 

思路：

代码:

class Solution {
public:
    vector<TreeLinkNode*> ans;
    void fun(TreeLinkNode* pHead){
        if(pHead->left) fun(pHead->left);
        ans.push_back(pHead);
        if(pHead->right) fun(pHead->right);
    }
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        if(!pNode) return NULL;
        TreeLinkNode* pHead=pNode;
        while(pHead->next) pHead=pHead->next;
        fun(pHead);
        for(int i=0;i<ans.size()-1;i++){
            if(ans[i]==pNode) return ans[i+1];
        }
        return NULL;
    }
};

算法二:

思路:

        分为两种情况：

            1.有右子树：

                    若右子树有左儿子，则找他的左儿子，若他的儿子有左儿子，则继续找，直到没有左儿子为止。

            2.没有右子树：

                    1.若它有祖先节点则找祖先节点，若满足该点在祖先节点左子树上，那么结束寻找直接返回该祖先节点。

                    2.若找到最后也找不到满足条件的祖先，说明没有下一个节点，那么返回NULL；

图解：

代码:

class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        if(!pNode) return NULL;
        if(pNode->right){
            TreeLinkNode* t=pNode->right;
            while(t->left){
                t=t->left;
            }
            return t;
        }
        while(pNode->next){
            if(pNode->next->left==pNode) return pNode->next;
            pNode=pNode->next;
        }
        return NULL;
    }
};