题解 | #重建二叉树#

树的结构：

/**
 * 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 [] in) {
        if (pre != null) 
            return doBuild(pre, in, 0, pre.length-1, 0, in.length-1);
        else 
            return null;
    }

    // 递归辅助函数
    private TreeNode doBuild(int[] pre, int[] in, int pl, int pr, int il, int ir) {
        if (pl < pr && il < ir) {
            TreeNode root = new TreeNode(pre[pl]);
            int rootIndex = index(in, il, ir, root.val);
            int sizeL = rootIndex - il;
            int sizeR = ir - rootIndex;
            if (sizeL > 0) {
                root.left = doBuild(pre, in, pl + 1, pl + sizeL, il, rootIndex-1); // 关键是找对相对位置
            }
            if (sizeR > 0) {
                root.right = doBuild(pre, in, pl+sizeL+1, pr, rootIndex+1, ir); // 关键是找对相对位置
            }
            return root;
        } 
        else if (pl == pr) 
            return new TreeNode(pre[pl]);
        else 
            return null;
    }

    private int index(int[] a, int il, int ir, int v) {
        for (int i = il; i <= ir; i++) {
            if (a[i] == v) return i;
        }
        return -1;
    }
}