分类讨论

• 分类讨论解决问题
• pNode为左节点 pNode->next|pNode->right
• pNode为右节点 pNode->right | 祖先节点 | 空
• pNode 为祖先节点 pNode->right | nullptr
• 漏了两种情况，导致报错

/*
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) {
        //pNode非空
        //分类讨论
        //pNode为左节点->pNode->next;
        //pNode为右节点 pNode->right | 祖先节点 | 空
        //pNode为中间节点 pNode->right
        // 祖先节点
        if(pNode->next)
        {
            //左
            if(pNode->next->left==pNode)
            {
                //左节点
                if(pNode->right)
                {
                    return pNode->right;
                }
                else{
                    return pNode->next;
                }
                
            }
            else{
                //右节点
                if(pNode->right)
                {
                    return pNode->right;
                }
                else{
                    //左子树
                    TreeLinkNode* cur=pNode->next,*front=pNode;
                    while(cur->next)
                    {
                        front=cur;
                        cur=cur->next;

                    }
                    if(front==cur->left)
                    {
                        return cur;
                    }
                    else{
                        //右子树
                        return nullptr;
                    }
                    //右子树
                }                
            }
        }
        else {
            //root节点
            if(pNode->right)
            {
                TreeLinkNode* cur=pNode->right;
                //左节点
                while(cur->left)
                {
                    cur=cur->left;
                }
                return cur;
            }
            else{
                return nullptr;
            }
        }
    }
};