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

class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        if (pNode == nullptr) return nullptr;

        // 1. 如果节点有右子树，下一个节点是右子树中的最左节点
        if (pNode->right != nullptr) {
            TreeLinkNode* nextNode = pNode->right;
            while (nextNode->left != nullptr) {
                nextNode = nextNode->left;
            }
            return nextNode;
        }

        // 2. 如果节点没有右子树(说明这一个子树（包含该节点的子树）已经走完了，若该子树为其根的左子树，则下一个为根；若该子树为其根的右子树，则说明已经全部遍历完了)
        while (pNode->next != nullptr) {
            TreeLinkNode* parent = pNode->next;
            if (parent->left == pNode) {
                return parent;
            }
            pNode = parent;
        }

        // 如果没有找到下一个节点，返回nullptr
        return nullptr;
    }
};