劍指offer【7】：重建二叉樹(shù)

?xiaoxiao, 發(fā)布于2019-08-16 18:41 / 1940人閱讀

摘要：例如，輸入前序遍歷序列和中序遍歷序列，則重建二叉樹(shù)并返回。題解對(duì)二叉樹(shù)前序中序遍歷的考察，采用遞歸的方法解決問(wèn)題，難點(diǎn)是確定每一個(gè)子樹(shù)的臨界點(diǎn)。

題目

輸入某二叉樹(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ì)二叉樹(shù)前序、中序遍歷的考察，采用遞歸的方法解決問(wèn)題，難點(diǎn)是確定每一個(gè)子樹(shù)的臨界點(diǎn)。

public class Solution {
    private Map map = new HashMap<>();
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        
        for(int i = 0; i< in.length; i++){
            map.put(in[i], i);
        }
        
        return reConstructBinaryTree(pre, 0, pre.length-1,0);
        
    }
    
    public TreeNode reConstructBinaryTree(int [] pre, int preL, int preR, int inL){
        //【易錯(cuò)點(diǎn)】=不可以寫(xiě)，等于說(shuō)明存在一個(gè)節(jié)點(diǎn)
        if(preL > preR){
            return null;
        }
        TreeNode root = new TreeNode(pre[preL]);
        int index = map.get(pre[preL]);
        int k = index - inL;
        root.left = reConstructBinaryTree(pre, preL+1, preL+k, inL);
        root.right = reConstructBinaryTree(pre, preL+k+1, preR, index+1);
        return root;
    }
    
    
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode(int x) { val = x; }
}

注意點(diǎn)

    if(preL > preR){
        return null;
    }

這里判斷條件不能有等于，等于相當(dāng)于該子樹(shù)只有一個(gè)節(jié)點(diǎn)

GPU云服務(wù)器云服務(wù)器二叉樹(shù) python二叉樹(shù) 平衡二叉樹(shù) 實(shí)現(xiàn)二叉樹(shù)

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

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

相關(guān)文章

【劍指offer】4.二叉樹(shù)的遍歷和重建

摘要：第一行為前序遍歷，第二行為中序遍歷。例如輸入前序遍歷序列和中序遍歷序列，則重建二叉樹(shù)并返回。根據(jù)前序遍歷和中序遍歷的結(jié)果可以拿到左子中序遍歷和右側(cè)為右子樹(shù)中序遍歷左子樹(shù)的前序遍歷和右子樹(shù)的前序遍歷然后遞歸左子樹(shù)和右子樹(shù)的完成重建。二叉樹(shù)簡(jiǎn)介基本結(jié)構(gòu)： function TreeNode(x) { this.val = x; this.left = null; ...

zhangyucha0 2019-08-23 14:40 評(píng)論0 收藏0
#yyds干貨盤(pán)點(diǎn)#劍指 Offer 07. 重建二叉樹(shù)

摘要：題目輸入某二叉樹(shù)的前序遍歷和中序遍歷的結(jié)果，請(qǐng)重建該二叉樹(shù)。例如，給出前序遍歷中序遍歷返回如下的二叉樹(shù)限制節(jié)點(diǎn)個(gè)數(shù)答案要使用這個(gè)方法，首先要將一個(gè)原始的數(shù)組，從下標(biāo)開(kāi)始復(fù)制，復(fù)制到上標(biāo)不包括，生成一個(gè)新的數(shù)組。題目輸入某二叉樹(shù)的前序遍歷和中序遍歷的結(jié)果，請(qǐng)重建該二叉樹(shù)。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不...

paney129 2021-11-24 09:39 評(píng)論0 收藏0
劍指Offer---根據(jù)前序遍歷和中序遍歷重建二叉樹(shù)

摘要：例如輸入前序遍歷序列和中序遍歷序列，則重建二叉樹(shù)并返回。代表前序數(shù)組，代表中序數(shù)組。中序遍歷的左右子樹(shù)比較好找，但是前序遍歷的左右子樹(shù)想到比較難找。 jdk 版本： jdk 1.8 題目：輸入某二叉樹(shù)的前序遍歷和中序遍歷的結(jié)果，請(qǐng)重建出該二叉樹(shù)。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,...

tainzhi 2019-08-16 10:53 評(píng)論0 收藏0
PHPer面試必看：分門(mén)別類帶你擼《劍指Offer》之二叉樹(shù)

摘要：例如輸入前序遍歷序列和中序遍歷序列，則重建二叉樹(shù)并返回。操作給定的二叉樹(shù)，將其變換為源二叉樹(shù)的鏡像。劍指中還有一道類似的變種題目，就是下面的這道，之字形遍歷二叉樹(shù)。最后下面的兩道題目分別運(yùn)用了二叉樹(shù)先序中序遍歷算法。開(kāi)篇以下內(nèi)容可能偏應(yīng)試但很好理解，所以大家一定要堅(jiān)持看下去，因?yàn)槲覀冏儚?qiáng)的過(guò)程注定孤獨(dú)的，堅(jiān)持下來(lái)就會(huì)看到明天的太陽(yáng)。回顧 showImg(https://user-...

li21 2019-07-01 10:26 評(píng)論0 收藏0
劍指offer(javascript版)

摘要：二維數(shù)組中的查找在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)。例如輸入前序遍歷序列和中序遍歷序列，則重建二叉樹(shù)并返回。 1.二維數(shù)組中的查找在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)...

imtianx 2019-08-20 15:20 評(píng)論0 收藏0