重建二叉树

使用库函数

class Solution {
    /**
    通过前序遍历中的第一个找到根结点，然后根据中序遍历结果根节点的左边为左子树，右边为右子树，
    然后两颗子树采用同样的方法找去到根节点
    **/
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0 || inorder.length == 0)
            return null;

        TreeNode node = new TreeNode(preorder[0]);

        for(int i = 0; i < inorder.length; i++){
            if(preorder[0] == inorder[i]){
                node.left = buildTree(Arrays.copyOfRange(preorder,1,i+1),Arrays.copyOfRange(inorder,0,i));
                node.right = buildTree(Arrays.copyOfRange(preorder,i+1,preorder.length),Arrays.copyOfRange(inorder,i+1,inorder.length));
                break;
            }
        }
        return node;
    }
}

使用ArrayList

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
    //把前序遍历的值和中序遍历的值放到list中
        List<Integer> preorderList = new ArrayList<>();
        List<Integer> inorderList = new ArrayList<>();
        for (int i = 0; i < preorder.length; i++) {
            preorderList.add(preorder[i]);
            inorderList.add(inorder[i]);
        }
        return builder(preorderList, inorderList);
    }

    private TreeNode builder(List<Integer> preorderList, List<Integer> inorderList) {
        if (inorderList.isEmpty())
            return null;
        //前序遍历的第一个值就是根节点
        int rootVal = preorderList.remove(0);

        //创建根结点
        TreeNode root = new TreeNode(rootVal);

        // 递归构建左右子树
        // 先找到根节点在中序遍历中的位置，进行划分
        int rootindex = inorderList.indexOf(rootVal);

        // 构建左子树，范围 [0:rootindex)
        root.left = builder(preorderList, inorderList.subList(0, rootindex));

        // 构建右子树，范围 (rootindex:最后的位置]
        root.right = builder(preorderList, inorderList.subList(rootindex + 1, inorderList.size()));
        // 返回根节点  
        return root;
    }
}