面试题8：二叉树的下一个节点（c++）【剑指offer】

/*
struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {

    }
};
*/
class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode){
        if(pNode==nullptr) return nullptr; //情况5

        if(pNode->right!=nullptr){ //情况1
            TreeLinkNode* newnode=pNode->right;
            while(newnode->left!=nullptr) newnode=newnode->left;
            return newnode;
        }

        else{
            if(pNode->next==nullptr) return nullptr; //情况2

            else{
                if(pNode->next->left==pNode) return pNode->next; //情况3

                else{ //情况4（复杂点），如节点i,g
                    TreeLinkNode* newnode=pNode->next;
                    while(( newnode->next!=nullptr) && (newnode->next->left!=newnode) ) newnode=newnode->next;
                    return newnode->next;
                }
            }
        }
    }
};