题目描述
思路解析
一句话答案：LeetCode 889 根据前序和后序遍历构造二叉树：前序开头必是根，前序第二个是左子树的根，去后序里定出左子树多大，把两个数组各切两半递归，哈希表定位做到 O(n)。
两个数组要还原成同一棵树
给你同一棵二叉树的前序遍历数组 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。一份输入可能对应好几棵树，返回任意一棵都算对。
光有前序，左右子树切在哪儿
假设手里只有前序。根是开头那个数，可根后面一长串里，前一段属于左子树、后一段属于右子树，中间那条分界线前序自己并不标出来。想还原只能挨个位置去假设「左子树占 k 个」，切开往下建，建不成再退回来换个 k，一棵 n 个节点的树试下来是指数级的功夫。若给的是前序加中序，中序能把根左右两边天然隔开，可这题给的是后序，得换个地方找分界线。
后序结尾框定左子树的大小
转机在后序。前序里根紧后面那个数 preorder[a+1]，就是左子树自己的根（前提是它有左子树）。后序会把一整棵左子树排在连续的一段里，左子树的根恰好落在这段的最末。拿 preorder[a+1] 去后序里查它排第几位，从段首数到它就是左子树的节点数，右边剩下的全归右子树。每次现扫后序是 O(n)、整体滑到 O(n²)；先把后序每个值映射到下标存进哈希表 pos，查位置只要 O(1)。
每一段递归各自建好一棵子树
写成一个递归 dfs，它盯着前序的一个区间和后序的一个区间，这两段是同一棵子树的两种排法。区间空了返回空；只剩一个数就是叶子，直接建好返回、不再往下取。否则拿前序开头 preorder[a] 建根，用 preorder[a+1] 在后序里的位置算出左子树大小 m。左子树递归前序接下来的 m 个配后序对应段，右子树递归前序剩下的配后序去掉末尾根的一段。孩子建好挂到根下，返回这个根。
拿题面这棵 7 节点树切一遍
回到题面这棵树。前序开头 50 是根，后面的 30 是左子树的根；30 在后序里排第 3 个（前面是 20、40），左子树占 3 个节点，前序后序据此各切成左右两半递归。左段根 30，20 在后序里排第 1 个、左子树只 1 个，于是 20 当左孩子、40 当右孩子，都成叶子返回。右段同理，根 80、左孩子 60、右孩子 90。全挂回去，读出的层序 50、30、80、20、40、60、90 正是题面要的那棵树。
少加一个 1，整段就会错位
最容易栽的是把左子树大小算成后序位置减区间起点、忘了加 1——位置差要加 1 才是元素个数，少算一个左右边界就整体挪位、往下全建歪。区间只剩一个数时别急着取 preorder[a+1]：那时它本就是叶子，硬取要么下标越界，要么把叶子误当成还带着左子树。前序加后序还定不出唯一的树——某节点只有一个孩子时挂左挂右两份序列一模一样、分不出来，题目才允许返回任意一种。时间上每个节点只建一次、查位置靠哈希表 O(1)，合计 O(n)；空间是哈希表加递归栈 O(n)。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这句口诀：前序第一个是根，前序第二个是左根，去后序定左子树大小，再切两半递归。下面每一帧都在套它。
准备 · 读入两个数组：开局树是空的。手里只有两个数组：前序 pre 和后序 post。前序的第一个 50 必是整棵树的根，咱们就从它开始切。
处理区间 · 7 个节点：现在处理被方括号框住的这一段，前序和后序各有 7 个数，它们正好是同一棵子树。先看前序开头。
建根 · 50：前序的第一个 50（紫色），就是这棵子树的根，先把它建出来放好。接着要分清谁是它的左子树、谁是右子树。
切分 · 左子树 3 个：50 后面紧挨的 30 就是它左子树的根。去后序里找 30，发现它排在第 3 个，说明左子树一共 3 个节点。据此把前序、后序都切成左、右两段，左边那段递归建左子树，右边那段建右子树。
处理区间 · 3 个节点：现在处理被方括号框住的这一段，前序和后序各有 3 个数，它们正好是同一棵子树。先看前序开头。
建根 · 30：前序的第一个 30（紫色），就是这棵子树的根，先把它建出来放好。接着要分清谁是它的左子树、谁是右子树。
切分 · 左子树 1 个：30 后面紧挨的 20 就是它左子树的根。去后序里找 20，发现它排在第 1 个，说明左子树一共 1 个节点。据此把前序、后序都切成左、右两段，左边那段递归建左子树，右边那段建右子树。
处理区间 · 1 个节点：现在处理被方括号框住的这一段，前序和后序各有 1 个数，它们正好是同一棵子树。先看前序开头。
建叶子 · 20：这一段只剩 20 一个数，没有左右可分，它就是一片叶子。直接建好挂上去，这一支到底了，返回。
处理区间 · 1 个节点：现在处理被方括号框住的这一段，前序和后序各有 1 个数，它们正好是同一棵子树。先看前序开头。
建叶子 · 40：这一段只剩 40 一个数，没有左右可分，它就是一片叶子。直接建好挂上去，这一支到底了，返回。
归位 · 30 的子树都建好：30 的左、右子树都递归建好并挂回到它下面，这棵子树完工，返回上一层继续。
处理区间 · 3 个节点：现在处理被方括号框住的这一段，前序和后序各有 3 个数，它们正好是同一棵子树。先看前序开头。
建根 · 80：前序的第一个 80（紫色），就是这棵子树的根，先把它建出来放好。接着要分清谁是它的左子树、谁是右子树。
切分 · 左子树 1 个：80 后面紧挨的 60 就是它左子树的根。去后序里找 60，发现它排在第 1 个，说明左子树一共 1 个节点。据此把前序、后序都切成左、右两段，左边那段递归建左子树，右边那段建右子树。
处理区间 · 1 个节点：现在处理被方括号框住的这一段，前序和后序各有 1 个数，它们正好是同一棵子树。先看前序开头。
建叶子 · 60：这一段只剩 60 一个数，没有左右可分，它就是一片叶子。直接建好挂上去，这一支到底了，返回。
处理区间 · 1 个节点：现在处理被方括号框住的这一段，前序和后序各有 1 个数，它们正好是同一棵子树。先看前序开头。
建叶子 · 90：这一段只剩 90 一个数，没有左右可分，它就是一片叶子。直接建好挂上去，这一支到底了，返回。
归位 · 80 的子树都建好：80 的左、右子树都递归建好并挂回到它下面，这棵子树完工，返回上一层继续。
完成 · 整棵树搭好：50 的左右子树都递归建好并接上了，整棵树就此还原完成，层序读出来正是 50、30、80、20、40、60、90。一次自顶向下的递归，每段都靠「前序定根、后序定大小」切两半。
回放 · 答案成形：回头看整个过程：每进入一段，前序第一个当根，前序第二个去后序定出左子树大小，切两半递归。最终还原出的树层序是 50、30、80、20、40、60、90，和目标完全一致。
边界先想清：单节点直接成树；只有一个孩子时按约定挂左边；两个孩子时靠后序定出各占几个。
面试重点：讲清「前序加后序为何不唯一」和「哈希表为何能降复杂度」。
参考代码
from __future__ import annotationsfrom 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 = rightclass 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 = rightclass 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)复杂度
- 时间：O(n)，先用哈希表存后序每个值的位置；之后每个节点只被建一次、每次查位置 O(1)，合计线性
- 空间：O(n)，哈希表 O(n) + 递归栈深 O(h)，最坏（退化成链）递归深 O(n)
易错点
面试追问把动画讲成自己的话
追问为什么前序加后序不能唯一确定二叉树，而前序加中序就可以？
追问为什么要用哈希表存后序的位置？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
所有可能的真二叉树
LeetCode 894 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题