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

  Definition for binary tree
  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
     TreeNode(int x) { val = x; }

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        
    }
}

• 思路：

  • 在二叉樹的前序遍歷序列中，第一個(gè)數(shù)字總是樹的根結(jié)點(diǎn)的值。但在中序遍歷序列中，根結(jié)點(diǎn)的值在序列的中間，左子樹的結(jié)點(diǎn)的值位于根結(jié)點(diǎn)的值的左邊，而右子樹的結(jié)點(diǎn)的值位于根結(jié)點(diǎn)的值的右邊。因此我們需要掃描中序遍歷序列，才能找到根結(jié)點(diǎn)的值。

  • 如下圖所示，前序遍歷序列的第一個(gè)數(shù)字1就是根結(jié)點(diǎn)的值。掃描中序遍歷序列，就能確定根結(jié)點(diǎn)的值的位置。根據(jù)中序遍歷特點(diǎn)，在根結(jié)點(diǎn)的值1前面的3個(gè)數(shù)字都是左子樹結(jié)點(diǎn)的值，位于1后面的數(shù)字都是右子樹結(jié)點(diǎn)的值。

    
    
    763943-20160909154257957-193477331.png
    • 同樣，在前序遍歷的序列中，根結(jié)點(diǎn)后面的3個(gè)數(shù)字就是3個(gè)左子樹結(jié)點(diǎn)的值，再后面的所有數(shù)字都是右子樹結(jié)點(diǎn)的值。這樣我們就在前序遍歷和中序遍歷兩個(gè)序列中，分別找到了左右子樹對應(yīng)的子序列。
    • 既然我們已經(jīng)分別找到了左、右子樹的前序遍歷序列和中序遍歷序列，我們可以用同樣的方法分別去構(gòu)建左右子樹。也就是說，接下來的事情可以用遞歸的方法去完成。
• 代碼：

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
         TreeNode root=reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
        return root;
    }
    //前序遍歷{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}
    private TreeNode reConstructBinaryTree(int [] pre,int startPre,int endPre,int [] in,int startIn,int endIn) {
          
        if(startPre>endPre||startIn>endIn)
            return null;
        TreeNode root=new TreeNode(pre[startPre]);
          
        for(int i=startIn;i<=endIn;i++)
            if(in[i]==pre[startPre]){
                root.left=reConstructBinaryTree(pre,startPre+1,startPre+i-startIn,in,startIn,i-1);
                root.right=reConstructBinaryTree(pre,i-startIn+startPre+1,endPre,in,i+1,endIn);
            }
                  
        return root;
    }
}