由中序周遊序列和前序周遊序列重建二叉樹

• 中序周遊
• 前序周遊
• 重建二叉樹思想
• 代碼實作

1.中序周遊

  在二叉樹中，中序周遊是一種很常見的周遊方式，首先周遊左子樹，然後根節點，最後右子樹。

2.前序周遊

  前序周遊是先周遊根節點，然後左子樹，最後右子樹。

3.重建二叉樹思想

  我們知道，前序周遊的第一個數字就是根節點，由根節點的值我們在中序周遊的序列中可以根據根節點的值區分出左子樹還有右子樹，以及每個子樹的結點的數目，然後我們由此在前序周遊的序列中劃分出相應的左右子樹，進行遞歸進行。

4.代碼實作

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}
public class Solution {
    //重建二叉樹
     public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
         if(pre==null||in==null) {
             return null;
         }
         //進入遞歸函數
         return reConstructTree(pre,,pre.length-,in,,in.length-);

     }

    public TreeNode reConstructTree(int[] pre, int startPre, int endPre, int[] in, int startIn, int endIn) {
        //判斷是否結束遞歸
        if(startPre>endPre|startIn>endIn) {
            return null;
        }
        int rootValue = pre[];
        TreeNode root=new TreeNode(rootValue);
        root.left=null;
        root.right=null;
        int indexIn=;
        //在中序周遊序列中找到根節點的位置
        for(int i=startIn;i<=endIn;i++) {
            if(in[i]==rootValue) {
                indexIn=i;
                break;
            }
        }
        //左子樹的結點個數
        int leftLength= indexIn-startIn;
        int leftPreEnd=startPre+leftLength;
        //遞歸左右子樹
        root.left=reConstructTree(pre,startPre+,leftPreEnd,in,startIn,indexIn-);
        root.right=reConstructTree(pre,leftPreEnd+,endPre,in,indexIn+,endIn);
        return root;
    }