首页 > 试题广场 >

二叉树的下一个结点

[编程题]二叉树的下一个结点
  • 热度指数：466076 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。下图为一棵有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示，从子节点指向父节点的用虚线表示

示例:
输入:{8,6,10,5,7,9,11},8
返回:9
解析:这个组装传入的子树根节点，其实就是整颗树，中序遍历{5,6,7,8,9,10,11}，根节点8的下一个节点就是9，应该返回{9,10,11}，后台只打印子树的下一个节点，所以只会打印9，如下图，其实都有指向左右孩子的指针，还有指向父节点的指针，下图没有画出来
数据范围：节点数满足 ，节点上的值满足

要求：空间复杂度 ，时间复杂度

输入描述:
输入分为2段，第一段是整体的二叉树，第二段是给定二叉树节点的值，后台会将这2个参数组装为一个二叉树局部的子树传入到函数GetNext里面，用户得到的输入只有一个子树根节点


输出描述:
返回传入的子树根节点的下一个节点，后台会打印输出这个节点
示例1

输入

{8,6,10,5,7,9,11},8

输出

9
示例2

输入

{8,6,10,5,7,9,11},6

输出

7
示例3

输入

{1,2,#,#,3,#,4},4

输出

1
示例4

输入

{5},5

输出

"null"

说明

不存在，后台打印"null"

说明：本题目包含复杂数据结构TreeLinkNode，点此查看相关信息
算法知识视频讲解
添加回答
推荐
牛客304487号头像 牛客304487号
分析二叉树的下一个节点，一共有以下情况：
1.二叉树为空，则返回空；
2.节点右孩子存在，则设置一个指针从该节点的右孩子出发，一直沿着指向左子结点的指针找到的叶子节点即为下一个节点；
3.节点不是根节点。如果该节点是其父节点的左孩子，则返回父节点；否则继续向上遍历其父节点的父节点，重复之前的判断，返回结果。代码如下：
class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode)
    {
        if(pNode==NULL)
            return NULL;
        if(pNode->right!=NULL)
        {
            pNode=pNode->right;
            while(pNode->left!=NULL)
                pNode=pNode->left;
            return pNode;
        }  
        while(pNode->next!=NULL)
        {
            TreeLinkNode *proot=pNode->next;
            if(proot->left==pNode)
                return proot;
            pNode=pNode->next;
        }
        return NULL;
    }
};
编辑于 2015-08-25 11:16:07 回复(49)
提交观点

问题信息

树
难度：
0条回答 106720浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号