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

zhangyucha0 发布于2019-08-23 14:40 / 2859人阅读

摘要：第一行为前序遍历，第二行为中序遍历。例如输入前序遍历序列和中序遍历序列，则重建二叉树并返回。根据前序遍历和中序遍历的结果可以拿到左子中序遍历和右侧为右子树中序遍历左子树的前序遍历和右子树的前序遍历然后递归左子树和右子树的完成重建。

二叉树简介

基本结构：

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

GPU云服务器云服务器二叉树的遍历二叉树的存储二叉树的存储结构 java二叉树的构建

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/100966.html

PHPer面试必看：分门别类带你撸《剑指Offer》之二叉树

摘要：例如输入前序遍历序列和中序遍历序列，则重建二叉树并返回。操作给定的二叉树，将其变换为源二叉树的镜像。剑指中还有一道类似的变种题目，就是下面的这道，之字形遍历二叉树。最后下面的两道题目分别运用了二叉树先序中序遍历算法。开篇以下内容可能偏应试但很好理解，所以大家一定要坚持看下去，因为我们变强的过程注定孤独的，坚持下来就会看到明天的太阳。回顾 showImg(https://user-...

li21 2019-07-01 10:26 评论0 收藏0
剑指Offer---根据前序遍历和中序遍历重建二叉树

摘要：例如输入前序遍历序列和中序遍历序列，则重建二叉树并返回。代表前序数组，代表中序数组。中序遍历的左右子树比较好找，但是前序遍历的左右子树想到比较难找。 jdk 版本： jdk 1.8 题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,...

tainzhi 2019-08-16 10:53 评论0 收藏0
剑指offer【7】：重建二叉树

摘要：例如，输入前序遍历序列和中序遍历序列，则重建二叉树并返回。题解对二叉树前序中序遍历的考察，采用递归的方法解决问题，难点是确定每一个子树的临界点。题目输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果都不含重复的数字。例如，输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。 ...

?xiaoxiao, 2019-08-16 18:41 评论0 收藏0
#yyds干货盘点#剑指 Offer 07. 重建二叉树

摘要：题目输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。例如，给出前序遍历中序遍历返回如下的二叉树限制节点个数答案要使用这个方法，首先要将一个原始的数组，从下标开始复制，复制到上标不包括，生成一个新的数组。题目输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不...

paney129 2021-11-24 09:39 评论0 收藏0
Java实现基本数据结构2（树）

摘要：实现基本数据结构栈，队列，链表这篇笔记侧重点二叉树的三种遍历前中后迭代非迭代代码重建二叉树的代码与分析和关于二叉树的题简单理解二叉查找树红黑树，的性质，实际用途。同时，以对应的节点为边界，就会把中序遍历的结果分为左子树和右子树。虽是读书笔记，但是如转载请注明出处 http://segmentfault.com/blog/exploring/ .. 拒绝伸手复制党以下是算法导论第十...

opengps 2019-08-14 12:06 评论0 收藏0