题解 | #重建二叉树#

算法思想一：递归
解题思路：
二叉树的前序遍历：根左右；中序遍历：左根右
由前序遍历知道根节点之后，能在中序遍历上划分出左子树和右子树。分别对中序遍历的左右子树递归进行这一过程即可建树。

图解：

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.length == 0 || vin.length == 0) {
            return null;
        }

        int root = pre[0];

        if (pre.length == 1) {
            return new TreeNode(root);
        }

        int midIndex = 0;

        //遍历中序数组 找出mid的根节点
        for (int i = 0; i < vin.length; i++) {

            if (vin[i] == root) {
                midIndex = i;
                break;
            }
        }

        TreeNode node = new TreeNode(root);

        node.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, midIndex + 1), Arrays.copyOfRange(vin, 0, midIndex));
        node.right = reConstructBinaryTree(Arrays.copyOfRange(pre, midIndex + 1, pre.length), Arrays.copyOfRange(vin, midIndex + 1, vin.length));

        return node;
    }
}