题解 | #二叉树的下一个结点#
二叉树的下一个结点
https://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e
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; } };