8剑指OFFER之2叉树的下一个节点

/*
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 == NULL)
            return NULL;
        
        
        //1.一个节点有右子树,那么它的下一个节点是该右子树中的最左节点
        if(pNode->right != NULL)
        {
            //该节点的右子树
             pNode = pNode->right;
            //判断不要写错了啊 是pNode->left 而不是pNode
            while(pNode->left != NULL)
            {
                pNode = pNode->left;
            }
            return pNode;
        }
       //2.一个节点没有右子树的话，分两种情况。
       //(1)它是它父节点的左子节点，那么下一个节点是该父节点
       //(2)否则的话，对该节点的父节点进行遍历，直到找到(1)
        while(pNode->next != NULL)
        {
             TreeLinkNode* pPar = pNode->next;
             if(pPar->left == pNode)
                return pPar;
             pNode =pNode->next;    
        }
        return NULL;
    }  

};