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

二叉树的下一个结点

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

全部评论

相关推荐

05-16 21:14
中南大学 Java
白火同学:说到底就是无实习的秋招、有实习的春招,哪个更难找到工作嘛。 现在离秋招还有两个半月时间,你现在可以一边背八股刷算法,一边投实习简历,看能不能拿到一份7-9月的实习。你这9本和技术栈找实习是够的,那你实习过程中继续优化简历。9月一边实习一边继续投秋招简历。
无实习如何秋招上岸
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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