【劍指offer】4.二叉樹的遍歷和重建

zhangyucha0 發(fā)布于2019-08-23 14:40 / 2895人閱讀

摘要：第一行為前序遍歷，第二行為中序遍歷。例如輸入前序遍歷序列和中序遍歷序列，則重建二叉樹并返回。根據(jù)前序遍歷和中序遍歷的結(jié)果可以拿到左子中序遍歷和右側(cè)為右子樹中序遍歷左子樹的前序遍歷和右子樹的前序遍歷然后遞歸左子樹和右子樹的完成重建。

二叉樹簡介

基本結(jié)構(gòu)：

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

二叉樹的前序、中序、后序遍歷的定義：

前序遍歷：對任一子樹，先訪問跟，然后遍歷其左子樹，最后遍歷其右子樹；

中序遍歷：對任一子樹，先遍歷其左子樹，然后訪問根，最后遍歷其右子樹；

后序遍歷：對任一子樹，先遍歷其左子樹，然后遍歷其右子樹，最后訪問根。

題目1 二叉樹遍歷 1.1 題目描述

給定一棵二叉樹的前序遍歷和中序遍歷，求其后序遍歷

輸入描述:

兩個字符串，其長度n均小于等于26。
第一行為前序遍歷，第二行為中序遍歷。
二叉樹中的結(jié)點名稱以大寫字母表示：A，B，C....最多26個結(jié)點。

輸出描述:

輸入樣例可能有多組，對于每組測試樣例，
輸出一行，為后序遍歷的字符串。

樣例：

輸入
ABC
BAC
FDXEAG
XDEFAG

輸出
BCA
XEDGAF

1.2 解題思路

前序遍歷：跟節(jié)點 + 左子樹前序遍歷 + 右子樹前序遍歷

中序遍歷：左子樹中序遍歷 + 跟節(jié)點 + 右字?jǐn)?shù)中序遍歷

后序遍歷：左子樹后序遍歷 + 右子樹后序遍歷 + 跟節(jié)點

1.前序遍歷的頭部為跟節(jié)點

2.中序遍歷以跟節(jié)點分割，左側(cè)為左子中序遍歷，右側(cè)為右子樹中序遍歷

3.根據(jù)中序遍歷得到的左子樹右子樹的長度，得到左子樹的前序遍歷和右子樹的前序遍歷

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 題目描述

輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建出該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。

例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并返回。

2.2 解題思路

思路和題目1相似。

根據(jù)前序遍歷和中序遍歷的結(jié)果可以拿到：

左子中序遍歷和右側(cè)為右子樹中序遍歷

左子樹的前序遍歷和右子樹的前序遍歷

然后遞歸左子樹和右子樹的完成重建。

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