【劍指offer】04 重建二叉樹

• 2020 年 12 月 23 日
• 筆記
• javascript, 劍指Offer

題目地址：重建二叉樹

題目描述                                   

輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重複的數字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹並返回。

時間限制：C/C++ 1秒，其他語言2秒 空間限制：C/C++ 64M，其他語言128M

題目示例                                   

輸入：

[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]

返回值：

{1,2,5,3,4,6,7}

解法分析                                   

通過前序和中序遍歷重建二叉樹，可以先找出root節點（也就是前序遍歷的pre[0]），然後在中序遍歷vin中找出root的位置，此時vin中root左側和右側的節點可以視為新的二叉樹——左側二叉樹和右側二叉樹，繼續對左側二叉樹和右側二叉樹用此方法直到沒有新的（子）二叉樹，即可得到重建的二叉樹。

很明顯，應該使用遞歸。

程式碼                                         

 1 /* function TreeNode(x) {
 2     this.val = x;
 3     this.left = null;
 4     this.right = null;
 5 } */
 6 function reConstructBinaryTree(pre, vin)
 7 {
 8     // write code here
 9     if(pre.length === 0 || vin.length === 0){
10         return null;
11     }
12     var root = vin.indexOf(pre[0]);
13     var left = vin.slice(0,root);
14     var right = vin.slice(root+1);
15     return{
16         val : pre[0],
17         left : reConstructBinaryTree(pre.slice(1,root+1),left),
18         right : reConstructBinaryTree(pre.slice(root+1),right)
19     };
20 }

執行結果