【剑指offer】4.二叉树的遍历和重建

2019-01-13 admin

二叉树简介

基本结构:

function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
}

二叉树的前序、中序、后序遍历的定义:

前序遍历:对任一子树,先访问跟,然后遍历其左子树,最后遍历其右子树;

中序遍历:对任一子树,先遍历其左子树,然后访问根,最后遍历其右子树;

后序遍历:对任一子树,先遍历其左子树,然后遍历其右子树,最后访问根。

题目1 二叉树遍历

1.1 题目描述

给定一棵二叉树的前序遍历和中序遍历,求其后序遍历

输入描述:

两个字符串,其长度n均小于等于26。 第一行为前序遍历,第二行为中序遍历。 二叉树中的结点名称以大写字母表示:A,B,C…最多26个结点。

输出描述:

输入样例可能有多组,对于每组测试样例, 输出一行,为后序遍历的字符串。

样例:

输入
ABC
BAC
FDXEAG
XDEFAG

输出
BCA
XEDGAF

1.2 解题思路

前序遍历:跟节点 + 左子树前序遍历 + 右子树前序遍历

中序遍历:左子树中序遍历 + 跟节点 + 右字数中序遍历

后序遍历:左子树后序遍历 + 右子树后序遍历 + 跟节点

1.前序遍历的头部为跟节点

2.中序遍历以跟节点分割,左侧为左子中序遍历,右侧为右子树中序遍历

3.根据中序遍历得到的左子树右子树的长度,得到左子树的前序遍历和右子树的前序遍历

1.3 代码

let pre;
let vin;

while((pre = readline())!=null){
    vin = readline();
    print(getHRD(pre,vin));
}

    function getHRD(pre, vin) {
      if (!pre) {
        return '';
      }
      if (pre.length === 1) {
        return pre;
      }
      const head = pre[0];
      const splitIndex = vin.indexOf(head);
      const vinLeft = vin.substring(0, splitIndex);
      const vinRight = vin.substring(splitIndex + 1);
      const preLeft = pre.substring(1, splitIndex + 1);
      const preRight = pre.substring(splitIndex + 1);
      return getHRD(preLeft, vinLeft) + getHRD(preRight, vinRight) + head;

题目2 二叉树重建

2.1 题目描述

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。

2.2 解题思路

思路和题目1相似。

根据前序遍历和中序遍历的结果可以拿到:

左子中序遍历和右侧为右子树中序遍历

左子树的前序遍历和右子树的前序遍历

然后递归左子树和右子树的完成重建。

2.3 代码

    function reConstructBinaryTree(pre, vin) {
        if(pre.length === 0){
            return null;
        }
        if(pre.length === 1){
            return new TreeNode(pre[0]);
        }
        const value = pre[0];
        const index = vin.indexOf(value);
        const vinLeft = vin.slice(0,index);
        const vinRight = vin.slice(index+1);
        const preLeft = pre.slice(1,index+1);
        const preRight = pre.slice(index+1);
        const node = new TreeNode(value);
        node.left = reConstructBinaryTree(preLeft, vinLeft);
        node.right = reConstructBinaryTree(preRight, vinRight);
        return node;
    }

原文链接:https://segmentfault.com/a/1190000017872751

本站文章除注明转载外,均为本站原创或编译。欢迎任何形式的转载,但请务必注明出处。

转载请注明:文章转载自 JavaScript中文网 [https://www.javascriptcn.com]

本文地址:https://www.javascriptcn.com/read-50900.html

文章标题:【剑指offer】4.二叉树的遍历和重建

相关文章
css布局的各种FC简单介绍:BFC,IFC,GFC,FFC
什么是FC? Formatting Context,格式化上下文,指页面中一个渲染区域,拥有一套渲染规则,它决定了其子元素如何定位,以及与其他元素的相互关系和作用。 BFC 什么是BFC Block Formatting Context,块...
2018-05-17
JavaScript实现PC手机端和嵌入式滑动拼图验证码三种效果
PC和手机端网站滑动拼图验证码效果源码,同时包涵了弹出式Demo,使用ajax形式提交二次验证码所需的验证结果值,嵌入式Demo,使用表单形式提交二次验证所需的验证结果值,移动端手动实现弹出式Demo三种效果 首先要确认前端使用页面,比如...
2017-03-17
Vue获取DOM元素样式和样式更改示例
在 vue 中用 document 获取 dom 节点进行节点样式更改的时候有可能会出现 ‘style’ is not definde的错误,这时候可以在 mounted 里用 $refs 来获取样式,并进行更改: <template...
2017-03-13
从2014年的发展来展望JS的未来将会如何
<font face="寰�杞�闆呴粦, Arial, sans-serif ">2014骞达紝杞�浠惰�屼笟鍙戝睍杩呴€燂紝鍚勭�嶈��瑷€灞傚嚭涓嶇┓锛屼互婊¤冻鐢ㄦ埛涓嶆柇鍙樺寲鐨勯渶姹傘€傝繖浜涜��...
2015-11-12
12个你未必知道的CSS小知识
虽然CSS并不是一种很复杂的技术,但就算你是一个使用CSS多年的高手,仍然会有很多CSS用法/属性/属性值你从来没使用过,甚至从来没听说过。 1.CSS的color属性并非只能用于文本显示 对于CSS的color属性,相信所有Web开发人员...
2015-11-12
ajax为什么令人惊异?ajax的优缺点
使用Ajax的最大优点,就是能在不更新整个页面的前提下维护数据。这使得Web应用程序更为迅捷地回应用户动作,并避免了在网络上发送那些没有改变的信息。 Ajax不需要任何浏览器插件,但需要用户允许JavaScript在浏览器上执行。就像DHT...
2015-11-12
HTML5的5个不错的开发工具推荐
HTML5规范终于在今年正式定稿,对于从事多年HTML5开发的人员来说绝对是一个重大新闻。数字天堂董事长,DCloud CEO王安也发表了文章,从开发者和用户两个角度分析了HTML对两个人群的优势。其实,关于HTML5的开发工具,我们以往的...
2015-11-12
JavaScript教程:JS中的原型
Keith Peters 几年前发表的一篇博文,关于学习没有“new”的世界,其中解释了使用原型继承代替构造函数。两者都是纯粹的原型编码。 标准方法(The Standard Way) 一直以来,我们学习的在 JavaScript 里创建对...
2015-11-12
AJAX的浏览器支持
AJAX 的要点是 XMLHttpRequest 对象。 不同的浏览器创建 XMLHttpRequest 对象的方法是有差异的。 IE 浏览器使用 ActiveXObject,而其他的浏览器使用名为 XMLHttpRequest 的 Jav...
2015-11-12
typeof、instanceof和contructor的区别
typeof:以字符串的形式返回变量的原始类型,typeof在两种情况下会返回"undefined":一个变量没有被声明的时候,和一个变量的值是undefined的时候,注意,typeof null也会返回object,...
2015-11-12
回到顶部