二叉树简介

基本结构：

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

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

前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树；

中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树；

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

题目1 二叉树遍历

1.1 题目描述

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

输入描述:

两个字符串，其长度n均小于等于26。

第一行为前序遍历，第二行为中序遍历。二叉树中的结点名称以大写字母表示：A，B，C....最多26个结点。

输出描述:

输入样例可能有多组，对于每组测试样例，

输出一行，为后序遍历的字符串。

样例：

输入ABCBACFDXEAGXDEFAG输出BCAXEDGAF

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