題目

根據(jù)樹的前序、中序遍歷構(gòu)建出樹結(jié)構(gòu)

題解

什么是前序、中序我就不帶大家復(fù)習(xí)了 根左右 左根右。

可愛的小樹

前序遍歷 [3,9,20,15,7]

中序遍歷 [9,3,15,20,7]

• 根據(jù)前序遍歷特點(diǎn) 我們能立刻得知，前序遍歷的第一個元素，即是這棵樹的根節(jié)點(diǎn)root節(jié)點(diǎn)，前序遍歷中 我們可以粗略把數(shù)組內(nèi)容分成3段：根、所有左元素、所有右元素（黃根、綠左、藍(lán)右）。

前序分隔

• 前序遍歷中，root節(jié)點(diǎn)的下一個節(jié)點(diǎn)即是第一個左孩子（即節(jié)點(diǎn)9），那第一個右孩子呢？
• 其實(shí)只要能夠計算出左元素個數(shù)我們就能根據(jù)root節(jié)點(diǎn)計算出第一個右孩子在前序遍歷中的相對位置 即 root節(jié)點(diǎn)下標(biāo)+ 左元素個數(shù) +1 即是第一個右孩子下標(biāo)

中序分隔

• root節(jié)點(diǎn)下標(biāo)是前序的第一個元素，那左元素個數(shù)我們怎么計算呢？我們不妨找到根節(jié)點(diǎn)在中序遍歷中的下標(biāo) 他的左側(cè)即是全部左元素，他的右側(cè)即是全部右元素。例如上圖：我們根據(jù)中序可以發(fā)現(xiàn)root節(jié)點(diǎn) 3左側(cè)有1個元素，那么在前序遍歷中，從根節(jié)點(diǎn)數(shù)起，向后數(shù)2位，即是第一個右子樹元素。
• 此時，我們已經(jīng)能夠構(gòu)建、獲取樹的root、第一個左、第一個右，我們只要把第一個左、第一個右當(dāng)作是新的root，進(jìn)行上述邏輯的遞歸，即可構(gòu)建出完整的樹。
• 但是有一點(diǎn)需要注意，在根據(jù)中序計算左右元素數(shù)量的時候應(yīng)當(dāng)控制元素邊界，每次以root將中序數(shù)組分割成3部分，全部左、root、全部右。

    private int [] preorder;
    private Map<Integer,Integer> map;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        map = new HashMap<>(inorder.length);
        for (int i=0;i<inorder.length;i++) map.put(inorder[i],i);
        return buildTree(0,0,preorder.length-1);
    }
    private TreeNode buildTree(int rootIndexForPre,int startIndexForIn,int endIndexForIn){
        if(startIndexForIn>endIndexForIn) return null;
        TreeNode root = new TreeNode(preorder[rootIndexForPre]);
        int rootIndexForIn = map.get(preorder[rootIndexForPre]);
        root.setLeft(buildTree(rootIndexForPre+1,startIndexForIn,rootIndexForIn-1));
        root.setRight(buildTree(rootIndexForIn-startIndexForIn+rootIndexForPre+1,rootIndexForIn+1,endIndexForIn));
        return root;
    }

源碼: 劍指offer4J