题目描述
思路解析动画文字版
记住这句口诀：前序第一个是根，前序第二个是左根，去后序定左子树大小，再切两半递归。下面每一帧都在套它。
准备 · 读入两个数组：开局树是空的。手里只有两个数组：前序 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题