Sword finger offer 57 Next node of binary tree

Cattle guest ：JZ57
Given a binary tree and one of its nodes , Please find the next node in the middle order traversal order and return . Be careful , The nodes in the tree contain not only left and right child nodes , It also contains a pointer to the parent node .

Analyze the next node of the binary tree , There are the following ：
1. The binary tree is empty , It returns null ;
2. Node right child exists , Set a pointer from the right child of the node , The leaf node found along the pointer to the left child node is the next node ;
3. Node is not root . If the node is the left child of its parent node , Then return to the parent node ; Otherwise, continue to traverse the parent node of its parent node upward , Repeat the previous judgment , Return results . The code is as follows ：

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