剑指offer_11 根据先序遍历和后序遍历构建二叉树

一、前序和后序遍历

二、题解

解题思路：
还是可以根据一般的思路，采用递归思想，对于每一个先序序列，划分出对应的根节点、左子树、右子树范围即可自上而下构建出二叉树。
例如对于上例中的先序序列[1,2,4,5,3,6,7]，第一个节点一定为根节点，第2到第i个节点为左子树，第i+1到最后一个节点为右子树，那么问题就可以简化为：如何确定左右子树分界点？

对于这个简化过后的问题，从后序遍历序列上很容易得到答案：

三、代码实现

public TreeNode constructFromPrePost(int[] pre, int[] post) {
        int N = pre.length;
        if (N == 0) return null;
        TreeNode root = new TreeNode(pre[0]);
        if (N == 1) return root;

        int L = 0;
        for (int i = 0; i < N; ++i)
            if (post[i] == pre[1])
                L = i+1;

        root.left = constructFromPrePost(Arrays.copyOfRange(pre, 1, L+1),
                                         Arrays.copyOfRange(post, 0, L));
        root.right = constructFromPrePost(Arrays.copyOfRange(pre, L+1, N),
                                          Arrays.copyOfRange(post, L, N-1));
        return root;
    }

作者：LeetCode
链接：https://leetcode-cn.com/problems/two-sum/solution/gen-ju-qian-xu-he-hou-xu-bian-li-gou-zao-er-cha-sh/
来源：力扣（LeetCode）

复杂度分析

时间复杂度：O(N^2)，其中 N是结点的数量。
空间复杂度：O(N^2)