剑指Offer面试题:5.重建二叉树

一题目:重建二叉树二思路先根据前序遍历序列的第一个数字创建根结点,接下来在中序遍历序列中找到根结点的位置,这样就能确定左、右子树结点的数量。在前序遍历和中序遍历的序列中划分了左、右子树结点的值

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

剑指Offer面试题:5.重建二叉树此处内容已经被作者隐藏,请输入验证码查看内容
验证码:
请关注本站微信公众号,回复“”,获取验证码。在微信里搜索“”或者“”或者微信扫描右侧二维码都可以关注本站微信公众号。

一 题目:重建二叉树

题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建出如下图所示的二叉树并输出它的头结点。

         
剑指Offer面试题:5.重建二叉树

二 思路

  先根据前序遍历序列的第一个数字创建根结点,接下来在中序遍历序列中找到根结点的位置,这样就能确定左、右子树结点的数量。在前序遍历和中序遍历的序列中划分了左、右子树结点的值之后,就可以递归地去分别构建它的左右子树。

三 代码实现

(1)索引实现

struct TreeNode
{
    int data;
    TreeNode* pLeft;
    TreeNode* pRight;
};

// 重构二叉树
TreeNode* RebulidTree(int *pre, int *mid, int len)
{
    if(NULL == pre || NULL == mid || len < 0)
    {
        return NULL;
    }
    // 根据前序遍历得到根节点
    int root = pre[0];
    TreeNode *pNode = new TreeNode;
    pNode->data = root;
    pNode->pLeft = pNode->pRight = NULL;
    
    int i = 0;
    // 根据根节点将中序遍历结果分成左子树和右子树,前提肯定能找到
    for (; i < len;i ++)
    {
        if (root == mid[i])
        {
            break;
        }
    }
    if (i > 0)
    {
        int *midleft = new int[i];
        memcpy(midleft, mid, sizeof(int) * i);
        int *preleft = new int[i];
        memcpy(preleft, &pre[1], sizeof(int)*i);
        pNode->pLeft = RebulidTree(preleft, midleft, i);
        delete[] midleft;
        delete[] preleft;
    }
    if (i < len-1)
    {
        int *midright = new int[len - i - 1];
        // 将中序分配左子树,右子树
        memcpy(midright, &mid[i+1], sizeof(int)*(len-i-1));
        // 将前序分配左子树和右子树
        int *preright = new int[len-i-1];
        memcpy(preright, &pre[i + 1], sizeof(int)*(len-i-1));
        pNode->pRight = RebulidTree(preright, midright, len - i - 1);
        delete[] midright;
        delete[] preright;
    }
    
    return pNode;
}

(2)指针实现

struct TreeNode
{
    int data;
    TreeNode* pLeft;
    TreeNode* pRight;
};

TreeNode* StructNode(int *StartPre, int *EndPre, int *StartMid, int *EndMid)
{
    // 根据前序遍历得到根节点
    int nRootValue = StartPre[0];
    TreeNode *pNode = new TreeNode;
    pNode->data = nRootValue;
    pNode->pLeft = pNode->pRight = NULL;

    if (StartPre == EndPre)
    {
        if ((StartMid == EndMid) && (*StartPre == *StartMid))
        {
            return pNode;
        }
        else
        {
            throw std::exception("Invalid input");
        }
    }
    // 在中序遍历中找到根结点的值
    int *RootMid = StartMid;
    while(RootMid < EndMid && *RootMid != nRootValue)
    {
        RootMid ++;
    }
    // 若没找到,抛出异常
    if(RootMid == EndMid && *RootMid != nRootValue)
    {
        throw std::exception("Invalid input");
    }

    int nLeftLength = RootMid - StartMid;
    int *LeftPreEnd = StartPre+nLeftLength;
    if (nLeftLength > 0)
    {
        pNode->pLeft = StructNode(++StartPre, LeftPreEnd, StartMid, RootMid-1);
    }
    if (nLeftLength < EndMid - StartMid)
    {
        pNode->pRight = StructNode(LeftPreEnd+1, EndPre,  RootMid+1, EndMid);
    }
    return pNode;
}

TreeNode* RebulidTree_2 (int *pre, int *mid, int len)
{
    if(NULL == pre || NULL == mid || len < 0)
    {
        return NULL;
    }

    return StructNode(pre, pre + len -1, mid, mid+len-1);
}

void main()
{
    int pre[] = {1,2,4,7,3,5,6,8};
    int mid[] = {4,7,2,1,5,3,8,6};

    TreeNode* p =RebulidTree_2(pre, mid, 8);
    return;
}

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/120170.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • php网页设计导航栏代码,总结7种常见的导航条制作实例

    php网页设计导航栏代码,总结7种常见的导航条制作实例导航条是网页设计中不可缺少的部分,它是指通过一定的技术手段,为网站的访问者提供一定的途径,使其可以方便地访问到所需的内容,是人们浏览网站时可以快速从一个页面转到另一个页面的快速通道。利用导航条,我们就可以快速找到我们想要浏览的页面。今天分享一下简单导航栏的制作方法:第一步:引入css样式表,新建一个id为nav的层,使用、、标签来制作完成效果。这篇文章主要为大家详细介绍了微信小程序实战之顶部导航栏…

  • 常见的嵌入式linux学习和如何选择ARM芯片问答

    常见的ARM嵌入式学习问答,设计者和学习者最关心的11个问题:1.      ARM嵌入式是学习硬件好还是学习软件好?2.      嵌入式软件和硬件,哪一种职位待遇更高?或者说,在设计中哪一个更重要?3.      学完51单片机后,想买ARM开发板继续学习,是买ARM7还是ARM9?4.      到底是学习哪种内核:ARM7、CORTEX-M3、COR

  • java工厂模式_java工厂模式

    java工厂模式_java工厂模式java工厂模式分三种:简单工厂模式、工厂方法模式、抽象工厂模式。简单工厂模式(SimpleFactoryPattern)属于类的创新型模式,又叫静态工厂方法模式(StaticFactoryMethodPattern),是通过专门定义一个类来负责创建其他类的实例,被创建的实例通常都具有共同的父类。简单工厂模式就是通过一个”全能类”,根据外界传递的信息来决定创建哪个具体类的对象。如下图(懒得…

  • C#后台调用前台javascript的五种方法

    C#后台调用前台javascript的五种方法

  • directx修复工具是干嘛的_win10自带dll修复

    directx修复工具是干嘛的_win10自带dll修复最后更新:2019-9-5ForEnglishversion,pleaserefertothebottomofthispage.DirectX修复工具最新版:DirectXRepairV3.9标准版NEW!版本号:V3.9.0.29371大小:30.7MB/7z格式压缩,98.7MB/zip格式压缩,231MB/解压后其他版本:增强版在…

  • JavaScript正则表达式简单教程「建议收藏」

    JavaScript正则表达式简单教程「建议收藏」1.常见的正则表达式符号?.匹配除换行符以外的任意字符\w匹配字母或数字或下划线或汉字\s匹配任意的空白符\d匹配数字\b匹配单词的开始和结束^匹配字符串的开始$匹配字符串的结束*重复零次或更多次+重复一次或更多次?重复零次或一次{n}重复n次{n,}重复n多次{n,m}重复n到m词\W匹配任意不是字母,数字,下划线,汉字的字符\S匹配任意不是空白符的字符\D匹配任意非数字的字符\B匹配不是单词开头或结尾的位置【^x】匹配除了x

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号