【刷算法】重建二叉樹(shù)

Blackjun 發(fā)布于2019-08-22 18:50 / 3438人閱讀

題目描述

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

分析

前序遍歷是中左右的順序，中序遍歷是左中右的順序，那么對(duì)于{1,2,4,7,3,5,6,8}和{4,7,2,1,5,3,8,6}來(lái)說(shuō)，1是根節(jié)點(diǎn)，然后1把中序遍歷的序列分割為兩部分，“4，7，2”為1的左子樹(shù)上的節(jié)點(diǎn)，“5，3，8，6”為1的右子樹(shù)上的節(jié)點(diǎn)，這樣遞歸的分解下去即可

代碼實(shí)現(xiàn)

/* 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;
}

云服務(wù)器 GPU云服務(wù)器二叉樹(shù)算法最優(yōu)二叉樹(shù)算法圖二叉樹(shù) python二叉樹(shù)

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/96262.html

相關(guān)文章

【刷算法】對(duì)稱(chēng)的二叉樹(shù)

摘要：題目描述請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，用來(lái)判斷一顆二叉樹(shù)是不是對(duì)稱(chēng)的。注意，如果一個(gè)二叉樹(shù)同此二叉樹(shù)的鏡像是同樣的，定義其為對(duì)稱(chēng)的。分析一般關(guān)于二叉樹(shù)的題目，第一直覺(jué)是往遞歸上面靠，當(dāng)然了，本題適不適合還暫時(shí)不知道。題目描述請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，用來(lái)判斷一顆二叉樹(shù)是不是對(duì)稱(chēng)的。注意，如果一個(gè)二叉樹(shù)同此二叉樹(shù)的鏡像是同樣的，定義其為對(duì)稱(chēng)的。分析一般關(guān)于二叉樹(shù)的題目，第一直覺(jué)是往遞歸上面靠，當(dāng)然了，本...

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

摘要：題目描述輸入一顆二叉樹(shù)和一個(gè)整數(shù)，打印出二叉樹(shù)中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。路徑定義為從樹(shù)的根結(jié)點(diǎn)開(kāi)始往下一直到葉結(jié)點(diǎn)所經(jīng)過(guò)的結(jié)點(diǎn)形成一條路徑。思路二叉樹(shù)的大多數(shù)問(wèn)題可以使用遞歸來(lái)解決，本題亦如此。題目描述輸入一顆二叉樹(shù)和一個(gè)整數(shù)，打印出二叉樹(shù)中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。路徑定義為從樹(shù)的根結(jié)點(diǎn)開(kāi)始往下一直到葉結(jié)點(diǎn)所經(jīng)過(guò)的結(jié)點(diǎn)形成一條路徑。思路二叉樹(shù)的大多數(shù)問(wèn)題可以使用...

zxhaaa 2019-08-22 18:21 評(píng)論0 收藏0
【刷算法】翻轉(zhuǎn)二叉樹(shù)的遞歸和非遞歸解法

摘要：題目描述操作給定的二叉樹(shù)，將其變翻轉(zhuǎn)為源二叉樹(shù)的鏡像。輸入描述解題思路遞歸版本首先，對(duì)數(shù)據(jù)結(jié)構(gòu)比較了解的話會(huì)想到用遞歸來(lái)解決。所謂遞歸，在計(jì)算機(jī)科學(xué)中是指一種通過(guò)重復(fù)將問(wèn)題分解為同類(lèi)的子問(wèn)題而解決問(wèn)題的方法來(lái)自維基百科。題目描述操作給定的二叉樹(shù)，將其變翻轉(zhuǎn)為源二叉樹(shù)的鏡像。輸入描述: 1 1 / ...

wangbjun 2019-08-22 18:06 評(píng)論0 收藏0
【刷算法】從上往下打印二叉樹(shù)

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

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

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

Joonas 2019-08-23 14:31 評(píng)論0 收藏0