【Check 55】2024-04-18 - 105. 从前序与中序遍历序列构造二叉树

[larscheng]

105. 从前序与中序遍历序列构造二叉树

[larscheng]

思路

前序遍历确定根节点，中序遍历确定左右子树，递归构建二叉树

代码

class Solution {
    //前序遍历确定根节点，中序遍历确定左右子树，递归构建二叉树
    //O(n)/O(n)
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length==0||inorder.length==0){
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        int rootIndex = Arrays.stream(inorder).boxed().collect(Collectors.toList()).indexOf(root.val);

        //[1,rootIndex+1]都是左子树
        root.left = buildTree(Arrays.copyOfRange(preorder, 1, rootIndex+1), Arrays.copyOf(inorder, rootIndex));
        //[rootIndex+1,lenght]都是右子树
        root.right = buildTree(Arrays.copyOfRange(preorder, rootIndex+1, preorder.length), Arrays.copyOfRange(inorder, rootIndex + 1, inorder.length));

        return root;
    }

}

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(n)