889. 根据前序和后序遍历构造二叉树
题目描述
输入两个整数数组 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]
解释：还原出的是一棵满二叉树：根 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来自同一棵二叉树。
解题思路：递归分治 + 哈希表定位左子树大小
前序的第一个数是根，第二个数是左子树的根。左子树的根在后序里是左子树的最后一个元素，所以它在后序中的位置能告诉我们左子树有多少个节点 size。据此把前序和后序都切成“根 | 左子树 | 右子树”三段，递归构造。只有一个孩子时无法区分左右，约定把它当作左孩子。
为什么正确
build(pl, pr, ql) 处理的前序片段 preorder[pl..pr] 与后序片段 postorder[ql..ql+(pr-pl)] 描述的是同一棵子树。
复杂度分析
时间 O(n)（哈希表查位置），空间 O(n)。
易错点
必须先判断 pl == pr（只剩一个节点）再访问 preorder[pl + 1]，否则会越界或误用右侧子树的元素。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
pos = {v: i for i, v in enumerate(postorder)}
def build(pl, pr, ql):
if pl > pr:
return None
root = TreeNode(preorder[pl])
if pl == pr:
return root
size = pos[preorder[pl + 1]] - ql + 1
root.left = build(pl + 1, pl + size, ql)
root.right = build(pl + size + 1, pr, ql + size)
return root
return build(0, len(preorder) - 1, 0)class Solution {
Map<Integer, Integer> pos = new HashMap<>();
int[] preorder;
TreeNode build(int pl, int pr, int ql) {
if (pl > pr) {
return null;
}
TreeNode root = new TreeNode(preorder[pl]);
if (pl == pr) {
return root;
}
int size = pos.get(preorder[pl + 1]) - ql + 1;
root.left = build(pl + 1, pl + size, ql);
root.right = build(pl + size + 1, pr, ql + size);
return root;
}
public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
this.preorder = preorder;
pos.clear();
for (int i = 0; i < postorder.length; i++) pos.put(postorder[i], i);
return build(0, preorder.length - 1, 0);
}
}class Solution {
public:
TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
unordered_map<int, int> pos;
for (int i = 0; i < (int)postorder.size(); i++) pos[postorder[i]] = i;
function<TreeNode*(int, int, int)> build = [&](int pl, int pr, int ql) -> TreeNode* {
if (pl > pr) {
return nullptr;
}
TreeNode* root = new TreeNode(preorder[pl]);
if (pl == pr) {
return root;
}
int size = pos[preorder[pl + 1]] - ql + 1;
root->left = build(pl + 1, pl + size, ql);
root->right = build(pl + size + 1, pr, ql + size);
return root;
};
return build(0, (int)preorder.size() - 1, 0);
}
};func constructFromPrePost(preorder []int, postorder []int) *TreeNode {
pos := map[int]int{}
for i, v := range postorder {
pos[v] = i
}
var build func(pl, pr, ql int) *TreeNode
build = func(pl, pr, ql int) *TreeNode {
if pl > pr {
return nil
}
root := &TreeNode{Val: preorder[pl]}
if pl == pr {
return root
}
size := pos[preorder[pl+1]] - ql + 1
root.Left = build(pl+1, pl+size, ql)
root.Right = build(pl+size+1, pr, ql+size)
return root
}
return build(0, len(preorder)-1, 0)
}var constructFromPrePost = function(preorder, postorder) {
const pos = new Map(postorder.map((v, i) => [v, i]));
const build = (pl, pr, ql) => {
if (pl > pr) {
return null;
}
const root = new TreeNode(preorder[pl]);
if (pl === pr) {
return root;
}
const size = pos.get(preorder[pl + 1]) - ql + 1;
root.left = build(pl + 1, pl + size, ql);
root.right = build(pl + size + 1, pr, ql + size);
return root;
};
return build(0, preorder.length - 1, 0);
};function constructFromPrePost(preorder: number[], postorder: number[]): TreeNode | null {
const pos = new Map<number, number>(postorder.map((v, i) => [v, i]));
const build = (pl: number, pr: number, ql: number): TreeNode | null => {
if (pl > pr) {
return null;
}
const root = new TreeNode(preorder[pl]);
if (pl === pr) {
return root;
}
const size = pos.get(preorder[pl + 1])! - ql + 1;
root.left = build(pl + 1, pl + size, ql);
root.right = build(pl + size + 1, pr, ql + size);
return root;
};
return build(0, preorder.length - 1, 0);
}其他解法
分治法先定位左子树大小再递归，是构造类题目的通用模板；栈模拟法把前序看成“进入结点”、后序看成“离开结点”，一遍扫描完成构造。
解法 2：栈模拟（前序入栈、后序出栈） 时间 O(n)，空间 O(h)
按前序依次创建结点，栈中保存从根到当前位置还没构造完的结点。新结点一定是栈顶的孩子：栈顶没有左孩子就挂在左边，否则挂在右边，然后入栈。用指针 j 指向后序中下一个应该结束的结点：只要栈顶等于 postorder[j]，说明它的子树已构造完，弹出并把 j 加 1。
不需要哈希表和下标区间计算，空间只和树高有关，也不会因递归过深而栈溢出。但“后序决定何时出栈”的正确性不如分治直观，需要理解两种遍历的时序关系。
class Solution:
def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
stack = []
j = 0
for v in preorder:
node = TreeNode(v)
if stack:
if stack[-1].left is None:
stack[-1].left = node
else:
stack[-1].right = node
stack.append(node)
while stack and stack[-1].val == postorder[j]:
root = stack.pop()
j += 1
return rootclass Solution {
public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode root = null;
int j = 0;
for (int v : preorder) {
TreeNode node = new TreeNode(v);
if (!stack.isEmpty()) {
if (stack.peek().left == null) stack.peek().left = node;
else stack.peek().right = node;
}
stack.push(node);
while (!stack.isEmpty() && stack.peek().val == postorder[j]) {
root = stack.pop();
j++;
}
}
return root;
}
}class Solution {
public:
TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
vector<TreeNode*> stk;
TreeNode* root = nullptr;
int j = 0;
for (int v : preorder) {
TreeNode* node = new TreeNode(v);
if (!stk.empty()) {
if (!stk.back()->left) stk.back()->left = node;
else stk.back()->right = node;
}
stk.push_back(node);
while (!stk.empty() && stk.back()->val == postorder[j]) {
root = stk.back();
stk.pop_back();
j++;
}
}
return root;
}
};func constructFromPrePost(preorder []int, postorder []int) *TreeNode {
stack := []*TreeNode{}
var root *TreeNode
j := 0
for _, v := range preorder {
node := &TreeNode{Val: v}
if len(stack) > 0 {
top := stack[len(stack)-1]
if top.Left == nil {
top.Left = node
} else {
top.Right = node
}
}
stack = append(stack, node)
for len(stack) > 0 && stack[len(stack)-1].Val == postorder[j] {
root = stack[len(stack)-1]
stack = stack[:len(stack)-1]
j++
}
}
return root
}var constructFromPrePost = function(preorder, postorder) {
const stack = [];
let root = null;
let j = 0;
for (const v of preorder) {
const node = new TreeNode(v);
if (stack.length > 0) {
const top = stack[stack.length - 1];
if (top.left === null) top.left = node;
else top.right = node;
}
stack.push(node);
while (stack.length > 0 && stack[stack.length - 1].val === postorder[j]) {
root = stack.pop();
j++;
}
}
return root;
};function constructFromPrePost(preorder: number[], postorder: number[]): TreeNode | null {
const stack: TreeNode[] = [];
let root: TreeNode | null = null;
let j = 0;
for (const v of preorder) {
const node = new TreeNode(v);
if (stack.length > 0) {
const top = stack[stack.length - 1];
if (top.left === null) top.left = node;
else top.right = node;
}
stack.push(node);
while (stack.length > 0 && stack[stack.length - 1].val === postorder[j]) {
root = stack.pop()!;
j++;
}
}
return root;
}