题解 | #重建二叉树#

一开始思路是比较清晰的，但是在写的时候没注意细节，调试花了比较多的时间。
有时候在ac过程中把代码擦除掉重新写比在原有代码增改更节省时间，因为有时候前后思路有差异，但是细节处理不到位。

解题思路：
[1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]

1. 从前序找出中间节点【1】，从中序根据中间节点拆分成两个二叉树【2，4，7】【3，5，6，8】，对应左节点和右节点。
2. 同理，两边节点也对应自己的前序和中序，重复环节1递归，知道只剩下一个节点。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.*;

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        if (pre.length == 0 || vin.length == 0) {
            return null;
        }
        int prePos = 0;
        int preLength = pre.length;
        int vinPos = 0;
        int vinLength = vin.length;
        return buildTree(pre, prePos, preLength, vin, vinPos, vinLength);
    }

    private TreeNode buildTree(int[] pre, int prePos, int preLength, 
                               int[] vin, int vinPos, int vinLength) {
        if (preLength <= 0) {
            return null;
        }
        int header = pre[prePos];
        TreeNode headerNode = new TreeNode(header);
        if (preLength == 1) {
            return headerNode;
        }

        int leftLength = 0;
        for (int i = 0; i < vinLength; i++) {
           if (vin[i + vinPos] == header) {
               break;
           } else {
               leftLength++;
           }
        }

        int newLeftPrePos = prePos + 1;
        int newLeftPreLength = leftLength;
        int newLeftVinPos = vinPos;
        int newLeftVinLength = leftLength;
        TreeNode leftNode = buildTree(pre, newLeftPrePos, newLeftPreLength, vin, newLeftVinPos, newLeftVinLength);
        headerNode.left = leftNode;

        int newRightPrePos = prePos + 1 + leftLength;
        int newRightPreLength = preLength - 1 - leftLength;
        int newRightVinPos = vinPos + 1 + leftLength;
        int newRightVinLength = vinLength - 1 - leftLength;
        TreeNode rightNode = buildTree(pre, newRightPrePos, newRightPreLength, vin, newRightVinPos, newRightVinLength);
        headerNode.right = rightNode;

        return headerNode;
    }
}