题解 | #重建二叉树#

/**
 * 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 node = new TreeNode(pre[preStart]);
      
        //中序遍历 找出左子树有多少个 左根右
        int rootIndex = 0;
        for (int i = middleStart; i <= middleEnd; i++) {
            if (node.val == middle[i]) {
                rootIndex = i;
                break;
            }
        }
        //  左子树
        int leftCount = rootIndex - middleStart;
        if(leftCount  > 0) {
            node.left = findNode(pre, preStart +1, preStart + leftCount, middle, middleStart, rootIndex-1);
        }
        int rightCount = middleEnd - rootIndex;
        if(rightCount > 0) {
            node.right = findNode(pre, preStart+leftCount+1, preEnd, middle,  rootIndex + 1, middleEnd);
        }
        return node;
    }
}