剑指57-二叉树的下一个结点

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

    }
};

class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode)
    {
        if (!pNode) return pNode;
        if (pNode->right) return inorderTraverse(pNode->right); //如果有右结点，下一个就是右子树的最左结点
        else if (pNode->next && pNode->next->left == pNode) { //如果没有右结点，而且是父节点的左结点
            return pNode->next;
        }
        else if (pNode->next && pNode->next->right == pNode) //如果没有右结点，而且是父节点的右结点
        {
            //这里是个难点，应该找到其祖先结点里，第一个该祖先结点为其父节点的左结点的这样一个结点，听起来有点拗口
            while (pNode->next) {
                TreeLinkNode *root = pNode->next;
                if (root->left == pNode) {
                    return root;
                }
                pNode = pNode->next;
            }
        }
        return nullptr;
    }

    TreeLinkNode* inorderTraverse(TreeLinkNode* root) //找到最左的结点
    {
        if (!root) return root;
        if (root->left) return inorderTraverse(root->left);
        else return root;
    }
};