问题描述
LeetCode 889. 根据前序和后序遍历构造二叉树 (opens in a new tab)，难度中等。
给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。
如果存在多个答案，您可以返回其中 任何 一个。
示例 1
输入：preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1] 输出：[1,2,3,4,5,6,7]
示例 2
输入: preorder = [1], postorder = [1] 输出: [1]
提示：
1 <= preorder.length <= 301 <= preorder[i] <= preorder.lengthpreorder中所有值都 不同postorder.length == preorder.length1 <= postorder[i] <= postorder.lengthpostorder中所有值都 不同- 保证
preorder和postorder是同一棵二叉树的前序遍历和后序遍历
题解
Solution.java
class Solution {
public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
int n;
if ((n = preorder.length) == 0) return null;
TreeNode root = new TreeNode(preorder[0]);
if (n == 1) return root;
int len = 0;
for (int i = 0; i < preorder.length; ++i) {
if (preorder[1] == postorder[i]) {
len = i + 1;
}
}
root.left = constructFromPrePost(Arrays.copyOfRange(preorder, 1, len + 1),
Arrays.copyOfRange(postorder, 0, len));
root.right = constructFromPrePost(Arrays.copyOfRange(preorder, len + 1, n),
Arrays.copyOfRange(postorder, len, n - 1));
return root;
}
}