34.重建二叉树

发表于 | 分类于

在学习JavaScript的一些总结和经验，供大家参考和学习，同时也欢迎大家参与讨论。

题目描述：

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

例1：

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

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例2：

前序遍历序列 [‘G’, ‘D’, ‘A’, ‘F’, ‘E’, ‘M’, ‘H’, ‘Z’]；

中序遍历序列 [‘A’, ‘D’, ‘E’, ‘F’, ‘G’, ‘H’, ‘M’, ‘Z’]，

则重建二叉树并返回，并求出后序遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
let preOrder  = ['G', 'D', 'A', 'F', 'E', 'M', 'H', 'Z'];
let inOrder = ['A', 'D', 'E', 'F', 'G', 'H', 'M', 'Z'];
// let preOrder= 'GDAFEMHZ';
// let inOrder = 'ADEFGHMZ';

function Node(key, left, right) {
    this.key = key;
    this.left = left;
    this.right = right;
}      
// 先根据先序遍历和中序遍历重构一棵二叉树
let len = preOrder.length;
function RefactorBinaryTree(preOrder, inOrder, len) {
   if(len != 0) { // 递归的终止条件（出口）

      var rootIndex = inOrder.indexOf(preOrder[0]); // 找到每一次递归，根节点在中序遍历中的位置

      let leftInOrder = inOrder.slice(0, rootIndex); // 中序左半部分（左子树）
      let rightInOrder = inOrder.slice(rootIndex + 1); // 中序右半部分（右子树）

      let leftTree = RefactorBinaryTree(preOrder.slice(1, leftInOrder.length + 1), leftInOrder, leftInOrder.length);    
      let rightTree = RefactorBinaryTree(preOrder.slice(leftInOrder.length + 1), rightInOrder, rightInOrder.length);

      let node = new Node(preOrder[0], leftTree, rightTree);
      return node;
  }
}
//后序遍历
function postOrder(node){
    if(node != null){
        postOrder(node.left);
        postOrder(node.right);
        console.log(node.key);
    }
}        

let newNode = RefactorBinaryTree(preOrder, inOrder, len);
console.log(newNode);
console.log(postOrder(newNode));


文章标题: 34.重建二叉树
文章作者: 王奕聪，QQ:1301842163
许可协议: 知识共享许可协议
©署名-非商用-相同方式共享 4.0