LeetCode 889中等树 · BST
根据前序和后序遍历构造二叉树 图解题解
这道题到底在问什么
给定无重复值二叉树的前序数组 preorder 与后序数组 postorder，重构并返回这棵二叉树。前序是「根，左，右」，后序是「左，右，根」。若有多种答案，返回任意一种即可。
- 输入
- preorder=[50,30,20,40,80,60,90], postorder=[20,40,30,60,90,80,50]
- 输出
- 层序 [50,30,80,20,40,60,90]
最优解：一步一步想明白
- 3记住这句口诀：前序第一个是根，前序第二个是左根，去后序定左子树大小，再切两半递归。下面每一帧都在套它。
- 4前序定根，后序定大小开局树是空的。手里只有两个数组：前序 pre 和后序 post。前序的第一个 50 必是整棵树的根，咱们就从它开始切。
- 5pre[0..6] / post[0..6]现在处理被方括号框住的这一段，前序和后序各有 7 个数，它们正好是同一棵子树。先看前序开头。
- 6前序第一个 = 根 = 50前序的第一个 50（紫色），就是这棵子树的根，先把它建出来放好。接着要分清谁是它的左子树、谁是右子树。
- 7左根 30 → 左子树 3 个50 后面紧挨的 30 就是它左子树的根。去后序里找 30，发现它排在第 3 个，说明左子树一共 3 个节点。据此把前序、后序都切成左、右两段，左边那段递归建左子树，右边那段建右子树。
- 8pre[1..3] / post[0..2]现在处理被方括号框住的这一段，前序和后序各有 3 个数，它们正好是同一棵子树。先看前序开头。
- 9前序第一个 = 根 = 30前序的第一个 30（紫色），就是这棵子树的根，先把它建出来放好。接着要分清谁是它的左子树、谁是右子树。
- 10左根 20 → 左子树 1 个30 后面紧挨的 20 就是它左子树的根。去后序里找 20，发现它排在第 1 个，说明左子树一共 1 个节点。据此把前序、后序都切成左、右两段，左边那段递归建左子树，右边那段建右子树。
- 11pre[2..2] / post[0..0]现在处理被方括号框住的这一段，前序和后序各有 1 个数，它们正好是同一棵子树。先看前序开头。
- 12区间只剩 1 个 → 叶子这一段只剩 20 一个数，没有左右可分，它就是一片叶子。直接建好挂上去，这一支到底了，返回。
- 13pre[3..3] / post[1..1]现在处理被方括号框住的这一段，前序和后序各有 1 个数，它们正好是同一棵子树。先看前序开头。
- 14区间只剩 1 个 → 叶子这一段只剩 40 一个数，没有左右可分，它就是一片叶子。直接建好挂上去，这一支到底了，返回。
- 1530 左右接好30 的左、右子树都递归建好并挂回到它下面，这棵子树完工，返回上一层继续。
- 16pre[4..6] / post[3..5]现在处理被方括号框住的这一段，前序和后序各有 3 个数，它们正好是同一棵子树。先看前序开头。
- 17前序第一个 = 根 = 80前序的第一个 80（紫色），就是这棵子树的根，先把它建出来放好。接着要分清谁是它的左子树、谁是右子树。
- 18左根 60 → 左子树 1 个80 后面紧挨的 60 就是它左子树的根。去后序里找 60，发现它排在第 1 个，说明左子树一共 1 个节点。据此把前序、后序都切成左、右两段，左边那段递归建左子树，右边那段建右子树。
- 19pre[5..5] / post[3..3]现在处理被方括号框住的这一段，前序和后序各有 1 个数，它们正好是同一棵子树。先看前序开头。
- 20区间只剩 1 个 → 叶子这一段只剩 60 一个数，没有左右可分，它就是一片叶子。直接建好挂上去，这一支到底了，返回。
- 21pre[6..6] / post[4..4]现在处理被方括号框住的这一段，前序和后序各有 1 个数，它们正好是同一棵子树。先看前序开头。
- 22区间只剩 1 个 → 叶子这一段只剩 90 一个数，没有左右可分，它就是一片叶子。直接建好挂上去，这一支到底了，返回。
- 2380 左右接好80 的左、右子树都递归建好并挂回到它下面，这棵子树完工，返回上一层继续。
- 24层序 = 50,30,80,20,40,60,9050 的左右子树都递归建好并接上了，整棵树就此还原完成，层序读出来正是 50、30、80、20、40、60、90。一次自顶向下的递归，每段都靠「前序定根、后序定大小」切两半。
- 25层序 [50,30,80,20,40,60,90]回头看整个过程：每进入一段，前序第一个当根，前序第二个去后序定出左子树大小，切两半递归。最终还原出的树层序是 50、30、80、20、40、60、90，和目标完全一致。
⚠️ 容易写错的地方
✗ 错：忘了 a 等于 b 的单节点情况就去取 preorder[a+1]
✓ 对：区间只剩一个先当叶子返回
否则 a+1 越界、或把叶子误当成有左子树
✗ 错：左子树大小算成 i 减 c（少加 1）
✓ 对：m = i 减 c 再加 1
位置差要加 1 才是元素个数，算少一个会整段错位
✗ 错：以为前序加后序能唯一确定一棵树
✓ 对：只有一个孩子时无法区分左右，本题允许返回任意一种
约定把 preorder[a+1] 当左孩子即可
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def constructFromPrePost(
self, preorder: List[int], postorder: List[int]
) -> Optional[TreeNode]:
def dfs(a: int, b: int, c: int, d: int) -> Optional[TreeNode]:
if a > b:
return None
root = TreeNode(preorder[a])
if a == b:
return root
i = pos[preorder[a + 1]]
m = i - c + 1
root.left = dfs(a + 1, a + m, c, i)
root.right = dfs(a + m + 1, b, i + 1, d - 1)
return root
pos = {x: i for i, x in enumerate(postorder)}
return dfs(0, len(preorder) - 1, 0, len(postorder) - 1)C++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
unordered_map<int, int> pos;
int n = postorder.size();
for (int i = 0; i < n; ++i) {
pos[postorder[i]] = i;
}
function<TreeNode*(int, int, int, int)> dfs = [&](int a, int b, int c, int d) -> TreeNode* {
if (a > b) {
return nullptr;
}
TreeNode* root = new TreeNode(preorder[a]);
if (a == b) {
return root;
}
int i = pos[preorder[a + 1]];
int m = i - c + 1;
root->left = dfs(a + 1, a + m, c, i);
root->right = dfs(a + m + 1, b, i + 1, d - 1);
return root;
};
return dfs(0, n - 1, 0, n - 1);
}
};Java
import java.util.*;
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
private Map<Integer, Integer> pos = new HashMap<>();
private int[] preorder;
public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
this.preorder = preorder;
for (int i = 0; i < postorder.length; ++i) {
pos.put(postorder[i], i);
}
return dfs(0, preorder.length - 1, 0, postorder.length - 1);
}
private TreeNode dfs(int a, int b, int c, int d) {
if (a > b) {
return null;
}
TreeNode root = new TreeNode(preorder[a]);
if (a == b) {
return root;
}
int i = pos.get(preorder[a + 1]);
int m = i - c + 1;
root.left = dfs(a + 1, a + m, c, i);
root.right = dfs(a + m + 1, b, i + 1, d - 1);
return root;
}
}复杂度
时间
O(n)
先用哈希表存后序每个值的位置；之后每个节点只被建一次、每次查位置 O(1)，合计线性
空间
O(n)
哈希表 O(n) + 递归栈深 O(h)，最坏（退化成链）递归深 O(n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 根据前序和后序遍历构造二叉树 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么前序加后序不能唯一确定二叉树，而前序加中序就可以？+
中序能把根的左右两边干净地分开，所以前序加中序唯一。前序加后序在「某个节点只有一个孩子」时会失去信息：这个孩子是左还是右，前序后序给出的序列完全一样，无法区分。所以本题才允许返回任意一种合法答案。
为什么要用哈希表存后序的位置？+
每次切分都要知道「左子树根」在后序里的下标，如果每次都线性扫一遍后序是 O(n)，整体退化到 O(n 方)。先花一遍把每个值映射到下标，之后查位置只要 O(1)，整体就降到 O(n)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 根据前序和后序遍历构造二叉树 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。