劍指offer——— JZ4、重建二叉樹

題目描述

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

示例1

輸入

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

傳回值

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

解題思路

比如示例中，前序周遊第一個數字為1，那麼1就是這個二叉樹的根節點。根據根節點為1，可以把中序周遊分成”1左邊，1，1右邊“三個部分。

就變成了：pre：1 234567   vin：324 1 657

會發現中序中324又是一個中序周遊，對應的先序周遊是先序周遊中1後面的三個數字234

現在變成了對pre：234 vin：324的兩個序列求二叉樹。

解決這個問題可以使用遞歸實作

代碼

首先先了解幾個JavaScript的函數：

JavaScript slice() 方法：

slice() 方法可從已有的數組中傳回標明的元素。

文法

arrayObject.slice(start,end)

參數	描述
start	必需。規定從何處開始選取。如果是負數，那麼它規定從數組尾部開始算起的位置。也就是說，-1 指最後一個元素，-2 指倒數第二個元素，以此類推。
end	可選。規定從何處結束選取。該參數是數組片斷結束處的數組下标。如果沒有指定該參數，那麼切分的數組包含從 start 到數組結束的所有元素。如果這個參數是負數，那麼它規定的是從數組尾部開始算起的元素。

傳回值

傳回一個新的數組，包含從 start 到 end （不包括該元素）的 arrayObject 中的元素。

說明

請注意，該方法并不會修改數組，而是傳回一個子數組。如果想删除數組中的一段元素，應該使用方法 Array.splice()。

提示和注釋

注釋：您可使用負值從數組的尾部選取元素。

注釋：如果 end 未被規定，那麼 slice() 方法會選取從 start 到數組結尾的所有元素。

<script type="text/javascript">

var arr = new Array(3)
arr[0] = "George"
arr[1] = "John"
arr[2] = "Thomas"

document.write(arr + "<br />")
document.write(arr.slice(1) + "<br />")
document.write(arr)

</script>
輸出：

George,John,Thomas
John,Thomas
George,John,Thomas
           

在本例中，我們将建立一個新數組，然後顯示從其中選取的元素：

<script type="text/javascript">

var arr = new Array(6)
arr[0] = "George"
arr[1] = "John"
arr[2] = "Thomas"
arr[3] = "James"
arr[4] = "Adrew"
arr[5] = "Martin"

document.write(arr + "<br />")
document.write(arr.slice(2,4) + "<br />")
document.write(arr)

</script>
輸出：

George,John,Thomas,James,Adrew,Martin
Thomas,James
George,John,Thomas,James,Adrew,Martin
           

JavaScript indexOf() 方法：

在本例中，我們将在 "Hello world!" 字元串内進行不同的檢索：

<script type="text/javascript">

var str="Hello world!"
document.write(str.indexOf("Hello") + "<br />")
document.write(str.indexOf("World") + "<br />")
document.write(str.indexOf("world"))

</script>
以上代碼的輸出：

0
-1
6
           

答案

function reConstructBinaryTree(pre, vin )
    {
        if(pre.length==0){
            return null;
        }
        let head=new TreeNode(pre[0]);
        let headindex=vin.indexOf(pre[0]);
        let vinleft=vin.slice(0,headindex);
        let vinright=vin.slice(headindex+1);
        let preleft=pre.slice(1,headindex+1);
        let preright=pre.slice(headindex+1);
        if(vinleft.length!=0){
            head.left=reConstructBinaryTree(preleft, vinleft);
        }
        if(vinright.length!=0){
            head.right=reConstructBinaryTree(preright,vinright);
        }
        return head;
    }
           

運作環境：JavaScript (V8 6.0.0)

運作時間：21ms

占用記憶體：6592KB