<strike id="saycc"></strike>

<del id="saycc"></del>

【刷算法】重建二叉樹

Blackjun 發布于2019-08-22 18:50 / 3444人閱讀

題目描述

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

分析

前序遍歷是中左右的順序，中序遍歷是左中右的順序，那么對于{1,2,4,7,3,5,6,8}和{4,7,2,1,5,3,8,6}來說，1是根節點，然后1把中序遍歷的序列分割為兩部分，“4，7，2”為1的左子樹上的節點，“5，3，8，6”為1的右子樹上的節點，這樣遞歸的分解下去即可

代碼實現

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function reConstructBinaryTree(pre, vin)
{
    var root = recon(0, pre.length-1, pre, 0, vin.length-1, vin);
    return root;
}

function recon(preStart, preEnd, pre, vinStart, vinEnd, vin){
    if(preStart > preEnd || vinStart > vinEnd) {
        return null;
    }

    var node = new TreeNode(pre[preStart]);

    for(var i = vinStart;i <= vinEnd;i++) {
        if(vin[i] === pre[preStart]){
            node.left = recon(preStart+1, preStart+i-vinStart, pre, vinStart, i-1, vin);
            node.right = recon(preStart+i-vinStart+1, preEnd, pre, i+1, vinEnd, vin);
        }
    }

    return node;
}

GPU云服務器云服務器二叉樹算法最優二叉樹算法圖二叉樹 python二叉樹

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/96262.html

【刷算法】對稱的二叉樹

摘要：題目描述請實現一個函數，用來判斷一顆二叉樹是不是對稱的。注意，如果一個二叉樹同此二叉樹的鏡像是同樣的，定義其為對稱的。分析一般關于二叉樹的題目，第一直覺是往遞歸上面靠，當然了，本題適不適合還暫時不知道。題目描述請實現一個函數，用來判斷一顆二叉樹是不是對稱的。注意，如果一個二叉樹同此二叉樹的鏡像是同樣的，定義其為對稱的。分析一般關于二叉樹的題目，第一直覺是往遞歸上面靠，當然了，本...

Forest10 2019-08-22 18:15 評論0 收藏0
【刷算法】二叉樹中和為某一值的路徑

摘要：題目描述輸入一顆二叉樹和一個整數，打印出二叉樹中結點值的和為輸入整數的所有路徑。路徑定義為從樹的根結點開始往下一直到葉結點所經過的結點形成一條路徑。思路二叉樹的大多數問題可以使用遞歸來解決，本題亦如此。題目描述輸入一顆二叉樹和一個整數，打印出二叉樹中結點值的和為輸入整數的所有路徑。路徑定義為從樹的根結點開始往下一直到葉結點所經過的結點形成一條路徑。思路二叉樹的大多數問題可以使用...

zxhaaa 2019-08-22 18:21 評論0 收藏0
【刷算法】翻轉二叉樹的遞歸和非遞歸解法

摘要：題目描述操作給定的二叉樹，將其變翻轉為源二叉樹的鏡像。輸入描述解題思路遞歸版本首先，對數據結構比較了解的話會想到用遞歸來解決。所謂遞歸，在計算機科學中是指一種通過重復將問題分解為同類的子問題而解決問題的方法來自維基百科。題目描述操作給定的二叉樹，將其變翻轉為源二叉樹的鏡像。輸入描述: 1 1 / ...

wangbjun 2019-08-22 18:06 評論0 收藏0
【刷算法】從上往下打印二叉樹

摘要：題目描述從上往下打印出二叉樹的每個節點，同層節點從左至右打印。分析二叉樹的層次遍歷，可以借助隊列的幫助實現題目描述從上往下打印出二叉樹的每個節點，同層節點從左至右打印。分析二叉樹的層次遍歷，可以借助隊列的幫助實現 /* function TreeNode(x) { this.val = x; this.left = null; this.right =...

ShowerSun 2019-08-22 18:20 評論0 收藏0
【刷算法】LeetCode.236-二叉樹的最近公共祖先

摘要：給定一個二叉樹找到該樹中兩個指定節點的最近公共祖先。示例輸入輸出解釋節點和節點的最近公共祖先是節點。說明所有節點的值都是唯一的。給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先。示例 1: 輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 輸出: 3 解釋: 節點 5 和節點 1 的最近公共祖先是節點 3。示例 ...

Joonas 2019-08-23 14:31 評論0 收藏0