4、重建二叉树------------>剑指offer系列

朴灿烈づ我的快乐病毒、 2021-12-24 01:35 205阅读 0赞

## 题目1-二叉树重建 ##

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

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

## 思路 ##

*  前序遍历：跟节点 + 左子树前序遍历 + 右子树前序遍历
 *  中序遍历：左子树中序遍历 + 跟节点 + 右字数中序遍历
 *  后序遍历：左子树后序遍历 + 右子树后序遍历 + 跟节点

根据上面的规律：

*  前序遍历找到根结点`root`
 *  找到`root`在中序遍历的位置 -> 左子树的长度和右子树的长度
 *  截取左子树的中序遍历、右子树的中序遍历
 *  截取左子树的前序遍历、右子树的前序遍历
 *  递归重建二叉树

[![E9_87_8D_E5_BB_BA_E4_BA_8C_E5_8F_89_E6_A0_91.png][]][E9_87_8D_E5_BB_BA_E4_BA_8C_E5_8F_89_E6_A0_91.png 1]

## 代码 ##

#    题目2-求二叉树的遍历 #

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

输入描述:

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

输出描述:

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

样例：

输入
    ABC
    BAC
    FDXEAG
    XDEFAG
    
    输出
    BCA
    XEDGAF

## 思路 ##

和上面题目的思路基本相同

*  前序遍历找到根结点`root`
 *  找到`root`在中序遍历的位置 -> 左子树的长度和右子树的长度
 *  截取左子树的中序遍历、右子树的中序遍历
 *  截取左子树的前序遍历、右子树的前序遍历
 *  递归拼接二叉树的后序遍历

## 代码 ##

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

![1476644-20190520203518286-799343798.png][]

![1476644-20190520203547473-853098521.png][]

![loading.gif][]![1476644-20190520203917554-1017868830.png][]

转载于:https://www.cnblogs.com/QianDingwei/p/10896314.html

[E9_87_8D_E5_BB_BA_E4_BA_8C_E5_8F_89_E6_A0_91.png]: /images/20211223/582ac8ea177e456ca2503ae0120be0aa.png
[E9_87_8D_E5_BB_BA_E4_BA_8C_E5_8F_89_E6_A0_91.png 1]: https://github.com/ConardLi/awesome-coding-js/blob/master/dist/img/%E9%87%8D%E5%BB%BA%E4%BA%8C%E5%8F%89%E6%A0%91.png
[1476644-20190520203518286-799343798.png]: /images/20211223/a7f90c6c2a3f42809f33b7d392592176.png
[1476644-20190520203547473-853098521.png]: /images/20211223/d7a7720707524818ae510536b29d8d48.png
[loading.gif]: https://common.cnblogs.com/images/loading.gif
[1476644-20190520203917554-1017868830.png]: /images/20211223/5a0643a69b41463486917a186a431232.png