JZ7重建二叉樹

描述

給定節點數為 n 的二叉樹的前序遍歷和中序遍歷結果，請重建出該二叉樹並返回它的頭結點。
例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}
提示:
1.vin.length == pre.length
2.pre 和 vin 均無重覆元素
3.vin出現的元素均出現在 pre里
4.只需要返回根結點，系統會自動輸出整顆樹做答案對比

具體做法：

step 1：先根據前序遍歷第一個點建立根節點。
step 2：然後遍歷中序遍歷找到根節點在數組中的位置。
step 3：再按照子樹的節點數將兩個遍歷的序列分割成子數組，將子數組送入函數建立子樹。
step 4：直到子樹的序列長度為0，結束遞歸。

代碼

package mid.JZ7重建二叉樹;

import java.util.*;


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

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {
    public TreeNode reConstructBinaryTree(int[] pre, int[] vin) {
        int n = pre.length;
        int m = vin.length;
        if (n == 0 || m == 0) return null;

        //前序遍歷第一個為根節點
        TreeNode root = new TreeNode(pre[0]);
        for (int i = 0; i < vin.length; i++) {
            if (pre[0] == vin[i]) {
                //左子樹
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(vin, 0, i));
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(vin, i + 1, vin.length));
                break;
            }
        }
        return root;
    }
}