算法疑难(js实现)---2、重建二叉树

一、总结

一句话总结：

1、找到根节点（前序序列的第一个元素一定是根节点）

2、根据找到的根节点和中序序列，找到树的左子树和右子树

3、让左子树和右子树进行1、2步的递归操作，来构建左子树和右子树

function rebuildTree(qianXu,zhongXu){
    if(qianXu[0]){
        //1、找到根节点（前序序列的第一个元素一定是根节点）
        let rootVal=qianXu[0];//根节点的值

        //2、根据找到的根节点和中序序列，找到树的左子树和右子树
        //根节点在中序序列中的位置
        let index=zhongXu.indexOf(rootVal);

        //前序序列：左子树qianXu（1,index）,右子树qianXu（index+1,最后）
        //中序序列：左子树zhongXu（0,index-1）,右子树zhongXu（index+1,最后）


        //3、让左子树和右子树进行1、2步的递归操作，来构建左子树和右子树
        let leftTree=rebuildTree(qianXu.slice(1,index+1),zhongXu.slice(0,index));
        let rightTree=rebuildTree(qianXu.slice(index+1),zhongXu.slice(index+1));

        let root=new TreeNode(rootVal);
        root.left=leftTree;
        root.right=rightTree;
        return root;
    }
}

二、重建二叉树

博客对应课程的视频位置：2、重建二叉树
https://www.fanrenyi.com/video/20/238

 1 <!DOCTYPE html>
 2 <html lang="en">
 3 <head>
 4     <meta charset="UTF-8">
 5     <title>重建二叉树</title>
 6 </head>
 7 <body>
 8 <!--
 9 
10 需求：
11 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
12 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
13 例如输入前序遍历序列[1,2,4,7,3,5,6,8]和中序遍历序列[4,7,2,1,5,3,8,6]，
14 则重建二叉树并返回。
15 
16 前序遍历序列：根左右：1,2,4,7,3,5,6,8
17 中序遍历序列：左根右：4,7,2,1,5,3,8,6
18 
19 思路：
20 1、找到根节点（前序序列的第一个元素一定是根节点）
21 2、根据找到的根节点和中序序列，找到树的左子树和右子树
22 3、让左子树和右子树进行1、2步的递归操作，来构建左子树和右子树
23 
24 根节点 为1
25 左子树
26 左子树的前序序列：根左右：2,4,7
27 左子树的中序序列：左根右：4,7,2
28 
29 节点2的左子树
30 左子树的前序序列：根左右：4,7
31 左子树的中序序列：左根右：4,7
32 
33 
34 右子树
35 右子树的前序序列：根左右：3,5,6,8
36 右子树的中序序列：左根右：5,3,8,6
37 
38 节点3的右子树
39 右子树的前序序列：根左右：6,8
40 右子树的中序序列：左根右：8,6
41 
42 算法思路：
43 递归
44 
45 -->
46 <script>
47     let qianXu=[1,2,4,7,3,5,6,8];
48     let zhongXu=[4,7,2,1,5,3,8,6];
49 
50     //在js中创建树的节点可以用构造函数
51     function TreeNode(val){
52         this.val=val;
53         this.left=null;
54         this.right=null;
55     }
56 
57     function rebuildTree(qianXu,zhongXu){
58         if(qianXu[0]){
59             //1、找到根节点（前序序列的第一个元素一定是根节点）
60             let rootVal=qianXu[0];//根节点的值
61 
62             //2、根据找到的根节点和中序序列，找到树的左子树和右子树
63             //根节点在中序序列中的位置
64             let index=zhongXu.indexOf(rootVal);
65 
66             //前序序列：左子树qianXu（1,index）,右子树qianXu（index+1,最后）
67             //中序序列：左子树zhongXu（0,index-1）,右子树zhongXu（index+1,最后）
68 
69 
70             //3、让左子树和右子树进行1、2步的递归操作，来构建左子树和右子树
71             let leftTree=rebuildTree(qianXu.slice(1,index+1),zhongXu.slice(0,index));
72             let rightTree=rebuildTree(qianXu.slice(index+1),zhongXu.slice(index+1));
73 
74             let root=new TreeNode(rootVal);
75             root.left=leftTree;
76             root.right=rightTree;
77             return root;
78         }
79 
80 
81     }
82 
83     //rebuildTree(qianXu,zhongXu);
84     console.log(rebuildTree(qianXu,zhongXu));
85 
86 
87 
88 
89 </script>
90 </body>
91 </html>