劍指offer【7】：重建二叉樹

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

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

題目

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

題解

對二叉樹前序、中序遍歷的考察，采用遞歸的方法解決問題，難點是確定每一個子樹的臨界點。

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){
        //【易錯點】=不可以寫，等于說明存在一個節(jié)點
        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; }
}

注意點

    if(preL > preR){
        return null;
    }

這里判斷條件不能有等于，等于相當于該子樹只有一個節(jié)點

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

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

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/75565.html

相關(guān)文章

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

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

zhangyucha0 2019-08-23 14:40 評論0 收藏0
#yyds干貨盤點#劍指 Offer 07. 重建二叉樹

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

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

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

tainzhi 2019-08-16 10:53 評論0 收藏0
PHPer面試必看：分門別類帶你擼《劍指Offer》之二叉樹

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

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

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

imtianx 2019-08-20 15:20 評論0 收藏0