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

二叉树的下一个结点

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;
    }
};

全部评论

相关推荐

吴offer选手:HR:我KPI到手了就行,合不合适关我什么事
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务