LeetCode-106

题目

结果

代码

标准版

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        // 特殊情况
        if (inorder.length == 0 || postorder.length == 0) {
            return null;
        }
        int root = postorder[postorder.length - 1];
        TreeNode ans = new TreeNode(root);

        // 计算根节点在inorder中的位置
        int index = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == root) {
                index = i;
                break;
            }
        }
        
        // 求得左子树的先序遍历和中序遍历结果，递归构造左子树
        int[] nextInOrderLeft = Arrays.copyOfRange(inorder, 0, index);
        int[] nextPostOrderLeft = Arrays.copyOf(postorder, nextInOrderLeft.length);
        ans.left = buildTree(nextInOrderLeft, nextPostOrderLeft);
        
        // 求得右子树的先序遍历结果和中序遍历结果，递归构造右子树
        int[] nextInOrderRight = Arrays.copyOfRange(inorder, index + 1, inorder.length);
        int[] nextPostOrderRight = Arrays.copyOfRange(postorder, nextInOrderLeft.length, nextInOrderLeft.length + nextInOrderRight.length);
        ans.right = buildTree(nextInOrderRight, nextPostOrderRight);

        return ans;
    }
}

优化版

可以不new新的数组，传参时只传下标，能有效节省空间。考虑下标好麻烦，算了不想了。

复杂度

时间复杂度：应该挺慢的

空间复杂度：应该占用了很多空间