题解 | #二叉树的下一个结点#

/*
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) {
        TreeLinkNode *pNext = nullptr;
        if (pNode->right != nullptr) {
            TreeLinkNode *pRight = pNode->right;
            while (pRight->left != nullptr) {
                pRight = pRight->left;
            }
            pNext = pRight;
            return pNext;
        }

        TreeLinkNode *pCurrent = pNode;
        TreeLinkNode *pParent = pCurrent->next;

        while (pParent != nullptr && pParent->right == pCurrent) {
            pCurrent = pParent;
            pParent = pCurrent->next;
        }
        pNext = pParent;

        return pNext;
    }
};