题解 | #重建二叉树#TOP40

思路:
1.中序遍历 和 前序遍历
2.左子树 根 右子树 // 根 左子树 右子树
3.以前序遍历的第一个节点是根节点，在中序遍历中找出此根节点。计算出左子树的长度和右子树的长度。遍历递归即可。

import java.util.*;
/**
 * 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 [] vin) {
        if (pre == null || vin == null) {
            return null;
        }
        if(pre.length ==0 ||vin.length == 0){
            return null;
        }
       TreeNode node = findNode(pre,0,pre.length - 1,vin,0,vin.length - 1);
        return node;
    }
    public  TreeNode findNode(int[] pre, int preStart, int preEnd, int[] middle, int middleStart, int middleEnd) {
         //前序遍历 根 左 右
        //中序遍历 左 根 右
        //当前节点为根节点
        TreeNode root = new TreeNode(pre[preStart]);
        //计算出 此根节点再中序遍历中的位置
        int middleRootIndex = middleStart;
        for(int i = middleStart; i <= middleEnd; i++){
            if(middle[i] == pre[preStart]){
                //找到中序遍历的根节点了
                middleRootIndex = i;
            }
        }
        
        //构建左子树
        int leftCount = middleRootIndex - middleStart;
        if(leftCount > 0){
            root.left = findNode(pre,preStart + 1, preStart + leftCount, middle, middleStart, middleRootIndex - 1);
        }
        //构建右子树
        int rightCount = middleEnd - middleRootIndex;
        if(rightCount > 0){
            root.right = findNode(pre, preStart + leftCount + 1, preEnd, middle, middleRootIndex + 1, middleEnd);
        }
        
        return root;
    }
}