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

2. 二叉树的下一个节点

二叉树的下一个结点_牛客题霸_牛客网

题目描述:给定一个二叉树其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。

示例1:

输入:{8,6,10,5,7,9,11}, 8
返回:9

  1. 如果一个节点有右子树,那么它的下一个节点就是它的右子树的最左节点
  2. 如果一个节点没有右子树 如果该节点是父节点的左孩子节点,那么下一个节点就是该节点的父节点如果该节点是父节点的右孩子节点,那么就一直向上找它的父节点,直到找到一个节点,是父节点的左孩子节点,此时下一个该节点的下一个节点就是该节点的父节点。如果找到根节点了,就证明到最后了,没有下一个节点了。
class Solution 
{
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode) 
    {
        // 1.一个节点有右子树
        if(pNode->right != nullptr) {
            pNode = pNode->right;
            while(pNode->left != nullptr)
                pNode = pNode->left;
            return pNode;
        }
        auto parent = pNode->next;
        // 2.1没有右子树, 该节点是父节点的左孩子节点
        if(parent != nullptr && parent->left == pNode)
            return parent;
        // 2.2没有右子树, 该节点是父节点的右孩子节点
        while(parent != nullptr) {
            pNode = parent;
            parent = pNode->next;
            if(parent == nullptr)    break;
            if(pNode == parent->left)
                return parent;
        }
        return nullptr;
    }
};

全部评论

相关推荐

Lorn的意义:你这种岗位在中国现在要么牛马天天加班,要么关系户进去好吃好喝,8年时间,真的天翻地覆了,对于资本来说你就说一头体力更好的牛马,哎,退伍没有包分配你真的亏了。
点赞 评论 收藏
分享
牛客83700679...:简历抄别人的,然后再投,有反馈就是简历不行,没反馈就是学历不行,多投多改只要技术不差机会总会有的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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