NC12题解 | #重建二叉树#

递归解决

重要的是需要传递四个参数

public class Solution{
	public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        if (pre == null || in == null || pre.length == 0 || in.length == 0 || pre.length != in.length) {
            return null;
        }
        return construct(pre, in, 0, pre.length, 0, in.length);
    }

    public TreeNode construct(int[] pre, int[] in, int preS, int preE, int inS, int inE) {
        if (preS > preE) {
            return null;
        }
        if (preS == preE && preS < pre.length) {
            return new TreeNode(pre[preS]);
        }
        int index = 0;
        //根值
        int rootVal = in[preS];
        TreeNode root = new TreeNode(rootVal);
        //在in中定位到pre的第一个元素
        for (int i = 0; i < in.length; i++) {
            if (in[i] == pre[preS]) {
                index = i;
            }
        }
        //左个数
        int lLen = index - inS;
        //右个数
        int rLen = inE - index;
        //左子节点
        root.left = construct(pre, in, preS + 1, preS + lLen, inS, index - 1);
        //右子节点
        root.right = construct(pre, in, preS + lLen + 1, preE, index + 1, inE);
        return root;
    }
}

class TreeNode {
   int val;
   TreeNode left;
   TreeNode right;
   TreeNode(int x) { val = x; }
}