0 Basic

二叉树是什么?

每个节点最多有两个子节点（左子节点、右子节点）的树结构。

        1          ← 根节点 (root)
       / \
      2   3        ← 深度 1
     / \   \
    4   5   6      ← 深度 2（叶子节点）

Python节点定义

1class TreeNode:
2    def __init__(self, val=0, left=None, right=None):
3        self.val = val
4        self.left = left
5        self.right = right

四种遍历方式

 1# 前序遍历（Pre-order）：根 → 左 → 右
 2def preorder(root):
 3    if not root: return
 4    print(root.val)       # 先处理根
 5    preorder(root.left)
 6    preorder(root.right)
 7
 8# 中序遍历（In-order）：左 → 根 → 右
 9def inorder(root):
10    if not root: return
11    inorder(root.left)
12    print(root.val)       # 中间处理根
13    inorder(root.right)
14
15# 后序遍历（Post-order）：左 → 右 → 根
16def postorder(root):
17    if not root: return
18    postorder(root.left)
19    postorder(root.right)
20    print(root.val)       # 最后处理根
21
22# 层序遍历（Level-order）：BFS，逐层从左到右
23from collections import deque
24def levelorder(root):
25    if not root: return
26    queue = deque([root])
27    while queue:
28        node = queue.popleft()
29        print(node.val)
30        if node.left:  queue.append(node.left)
31        if node.right: queue.append(node.right)

记忆口诀： 前/中/后指的是根节点在遍历中的位置（前面、中间、后面），左右顺序永远是先左后右。

BST 的中序遍历是升序序列:BST问题的核心性质。

二叉树递归的两种思维模式

模式一：自顶向下（传参数下去）

从根节点开始，把信息通过参数传递给子节点。

1# 例：计算每个节点的深度
2def dfs(node, depth):
3    if not node: return
4    print(f"节点 {node.val} 的深度是 {depth}")
5    dfs(node.left, depth + 1)
6    dfs(node.right, depth + 1)

模式二：自底向上（从返回值收集信息）

先递归处理子树，用子树的返回值计算当前节点的答案。

1# 例：计算树的高度
2def height(node):
3    if not node: return 0
4    left_h = height(node.left)
5    right_h = height(node.right)
6    return max(left_h, right_h) + 1

二叉搜索树 (BST)

BST 的性质：对任意节点，左子树所有节点 < 当前节点 < 右子树所有节点
BST 的中序遍历 = 升序排列

1 层序遍历模板

1.1 二叉树的层序遍历 | Medium

题目：给二叉树的根节点 root ，返回其节点值的层序遍历，逐层返回节点值，每层一个列表

思路分析：BFS 标准模板

队列里存的是"待访问的节点"
怎么知道某个节点属于第几层？进入 while 循环时，队列里恰好是完整的一层
记下 size = len(q)，只弹出这么多个，弹的同时把下一层压进去

踩坑记录：

忘记先固定 size，边弹边压导致层混在一起
空树要先判断，否则 deque([None]) 会出错

代码：

 1class Solution:
 2    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
 3        if not root:
 4            return []
 5        
 6        res, q = [], deque([root])
 7        while q:
 8            size, level = len(q), []
 9            for _ in range(size):
10                node = q.popleft()
11                level.append(node.val)
12                if node.left:
13                    q.append(node.left)
14                if node.right:
15                    q.append(node.right)
16            res.append(level)
17
18        return res

复杂度：

时间 O(n)
空间 O(n)（队列最多存一层，最宽一层可达 n/2 个节点）

1.2 二叉树的右视图 | Medium

题目: 返回从右侧看到的节点值（每层最右边的节点），自顶向下

思路分析： BFS：参考层序遍历的模板，每层自取最后一个作为答案

DFS：按"根 → 右 → 左"的顺序遍历，携带深度参数。这个顺序下，每层第一个被访问到的节点就是最右边的那个。所以判断 depth == len(res)（说明这层还没有代表）时收录

踩坑记录：

DFS 版顺序写成"根左右"，收录的就是左视图
depth == len(res) 判断很精妙：res 的长度恰好等于"已经有代表的层数"

代码： plan 1: BFS

 1class Solution:
 2    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
 3        if not root:
 4            return []
 5
 6        res, q = [], deque([root])
 7        while q:
 8            res.append(q[-1].val)
 9            for _ in range(len(q)):
10                node = q.popleft()
11                if node.left:
12                    q.append(node.left)
13                if node.right:
14                    q.append(node.right)
15        return res

plan 2: DFS

 1class Solution:
 2    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
 3        res = []
 4        def dfs(node, depth):
 5            if not node:
 6                return 
 7            if depth == len(res):
 8                res.append(node.val)
 9            dfs(node.right, depth + 1)
10            dfs(node.left, depth + 1)
11        dfs(root, 0)
12        return res

复杂度：

时间 O(n)
空间 O(h)（BFS 版为 O(n)）

2 中序遍历模板

2.1 二叉树的中序遍历 | Easy

题目: 给定二叉树根节点，返回中序遍历（左→根→右）的节点值列表

思路分析： plan 1：递归版

递归顺序是左根右，本质是维护一个调用栈

plan 1：递归版

中序遍历（左根右）：从根节点一路向左出发（不是终点不访问，压栈），到底后访问它然后转向右子树，重复过程。
结束：stack为空且指针也为空

踩坑记录：

迭代版弹栈后忘记 cur = cur.right，死循环或漏访问右子树
循环条件写成 while stack，会漏掉最开始 cur 非空但栈还空的阶段；必须 while cur or stack

代码： plan 1：递归版

 1class Solution:
 2    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
 3        res = []
 4        def dfs(node):
 5            if not node:
 6                return
 7            dfs(node.left)
 8            res.append(node.val)
 9            dfs(node.right)
10        dfs(root)
11        return res

plan 2：迭代版

 1class Solution:
 2    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
 3        res, stack, cur = [], [], root
 4        while cur or stack:
 5            while cur:
 6                stack.append(cur)
 7                cur = cur.left
 8            cur = stack.pop()
 9            res.append(cur.val)
10            cur = cur.right
11        return res

复杂度：

递归：时间O(n) 空间O(n)
迭代：时间O(n) 空间O(n)

2.2 二叉搜索树中第 K 小的元素 | Meidum

题目: 返回 BST 中第 k 小的节点值

思路分析：

BST本身性质是中序递增 + 第k小 $\Rightarrow$ 中序遍历到第k个就是答案
迭代中序模板

踩坑记录：

记牢中序遍历模板

代码：

 1class Solution:
 2    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
 3        stack, cur = [], root
 4        while cur or stack:
 5            while cur:
 6                stack.append(cur)
 7                cur = cur.left
 8            cur = stack.pop()
 9            k -= 1
10            if k == 0:
11                return cur.val
12            cur = cur.right

复杂度：

时间 O(h + k)（先走到最左花 O(h)，再弹 k 次）
空间 O(h)

3 二叉树的深度和直径

3.1 二叉树的最大深度 | Easy

题目: 返回二叉树的最大深度（根到最远叶子的节点数）

思路分析：

空树深度为 0
深度 = 1 + max(left, right)

踩坑记录：

先写出递归函数的自然语言定义再动手

代码：

1class Solution:
2    def maxDepth(self, root: Optional[TreeNode]) -> int:
3        if not root:
4            return 0
5        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

复杂度：

时间 O(n)
空间 O(h)（递归栈）

3.2 二叉树的直径 | Easy

题目: 直径 = 任意两节点路径长度（边数）的最大值，路径不一定过根

思路分析：

经过某个节点的最长路径 = 节点左子树深度 + 节点右子树深度，直径就是所有节点最长路径的最大值，所以我需要算每个节点的最长路径
递归函数应该返回每个节点的深度

踩坑记录：

直径是按边算不是按节点算
直径不应该过root node

代码：

 1class Solution:
 2    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:    
 3        self.ans = 0
 4        def findDepth(node):
 5            if not node:
 6                return 0
 7            l, r = findDepth(node.left), findDepth(node.right)
 8            self.ans = max(self.ans, l + r)
 9            return 1 + max(l, r)
10        findDepth(root)
11        return self.ans

复杂度：

时间 O(n)
空间 O(h)

3.3 二叉树中的最大路径和 | Hard

题目: 路径 = 树中任意相连的节点序列（不能分叉、不必过根、至少一个节点），求路径和的最大值。节点值可为负。

思路分析：

经过节点 node 的最大路径和是什么？= node.val + 左子树的最大单边贡献 + 右子树的最大单边贡献。所谓"单边贡献"：从子树根出发一路向下的一条链的最大和
递归函数应该返回什么给父节点？不能返回"拐弯的路径"（父节点接不上），只能返回单边贡献：node.val + max(左贡献, 右贡献)
如果子树的贡献是负的，接上它还不如不接。所以贡献要和 0 取 max：L = max(0, gain(node.left))。这一步等价于"允许路径不延伸进该子树"

踩坑记录：

答案初始化是float("-inf"),考虑全负树的出现

代码：

 1class Solution:
 2    def maxPathSum(self, root: Optional[TreeNode]) -> int:
 3        self.ans = float("-inf")
 4
 5        def gain(node):
 6            if not node:
 7                return 0
 8            l = max(0, gain(node.left))
 9            r = max(0, gain(node.right))
10            self.ans = max(self.ans, node.val + l + r)
11            return node.val + max(l , r)
12        gain(root)
13
14        return self.ans

复杂度：

时间 O(n)
空间 O(h)

4 二叉树的左右递归处理

4.1 翻转二叉树 | Easy

题目: 翻转二叉树（所有节点的左右孩子互换），返回根

思路分析：递归视角：

根节点保持不变，左右子树已反转好，再交换左右子树

踩坑记录：

交换动作的顺序

代码：

1class Solution:
2    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
3        if not root:
4            return None
5        root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
6        return root

复杂度：

时间 O(n)
空间 O(h)

4.2 对称二叉树 | Easy

题目：判断二叉树是否轴对称（镜像对称）

思路分析: 左右子树镜像对称：

p.val == q.val
p.left和q.right互为镜像
p.right和q.left互为镜像

踩坑记录: base case:

都空：True
只有一个空: False
都不空：递归比较

代码：

1class Solution:
2    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
3        def isMirrors(p, q):
4            if not p and not q:
5                return True
6            if not p or not q:
7                return False
8            return (p.val == q.val and isMirrors(p.right, q.left) and isMirrors(p.left, q.right))
9        return isMirrors(root, root)

复杂度：

时间 O(n)
空间 O(h)

4.3 二叉树的最近公共祖先 | Medium

题目: 找 p、q 的最近公共祖先（LCA）。p、q 保证存在于树中。最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

思路分析：

root 就是 p 或 q → 直接返回 root
递归左右子树拿到 L、R：
- L、R 都非空 → p、q 分居两侧，root 就是 LCA
- 只有一边非空 → 答案（或那个单独的节点）在那一边，原样上传
- 都空 → None

踩坑记录：

想不通"root == p 时为什么不用继续找 q"：因为题目保证 q 存在，若 q 在 root 子树里，LCA 就是 root；若不在，root 会被上层作为"找到的那一个"上传，逻辑依然自洽
这个解法依赖"p、q 必存在"的前提；若不保证存在，需要额外判定

代码：

1class Solution:
2    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
3        if not root or p is root or q is root:
4            return root
5        left = self.lowestCommonAncestor(root.left, p, q)
6        right = self.lowestCommonAncestor(root.right, p, q)
7        if left and right:
8            return root
9        return left or right

复杂度：

时间 O(n)
空间 O(h)

5 序列和树的重构

5.1 从前序与中序遍历序列构造二叉树 | Medium

题目: 给定前序和中序序列（无重复值），构造原二叉树

思路分析：

前序的第一个元素一定是根（根左右）
在中序里找到根的位置 i，则中序中 i 左边是左子树的中序、右边是右子树的中序
左子树有 i - in_low 个节点，据此把前序也切成两段
递归左右子树

踩坑记录：

p的处理：self.p or nonlocal p

代码：

 1class Solution:
 2    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
 3        idx = {v:i for i, v in enumerate(inorder)}
 4        p = 0
 5
 6        def build(low, high):
 7            nonlocal p
 8            if low > high:
 9                return None
10            node = TreeNode(preorder[p])
11            mid = idx[preorder[p]]
12            p += 1
13            node.left = build(low, mid - 1)
14            node.right = build(mid + 1, high)
15            return node
16
17        return build(0, len(inorder) - 1)

复杂度：

时间 O(n)（哈希查根 O(1)）
空间 O(n)（哈希表 + 递归栈

5.2 从中序与后序遍历序列构造二叉树 | Medium

题目: 给定后序和中序序列（无重复值），构造原二叉树

思路分析：

前序: 根左右 $\Rightarrow$ 根在最前,消费完根,紧接着的是左子树
后序: 左右根 $\Rightarrow$ 根在最后,消费完根,紧邻它前面的是右子树

踩坑记录：

注意建树顺序

代码：

 1class Solution:
 2    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
 3        idx = {v:i for i, v in enumerate(inorder)}
 4        p = len(postorder) - 1
 5
 6        def build(low, high):
 7            nonlocal p
 8            if low > high:
 9                return 
10            node = TreeNode(postorder[p])
11            mid = idx[postorder[p]]
12            p -= 1
13            node.right = build(mid + 1, high)
14            node.left = build(low, mid - 1)
15            return node
16
17        return build(0, len(inorder) - 1)

5.3 将有序数组转换为二叉搜索树 | Easy

题目: 升序数组转为平衡 BST

思路分析：

BST 中序遍历 = 升序数组，所以数组就是目标树的中序序列
要平衡，左右子树节点数要尽量均等。那根应该选谁？数组中点。选完中点，左半段构造左子树、右半段构造右子树，天然递归

踩坑记录：

low > high 是 base case，返回 None；写成 low >= high 会丢节点

代码：

 1class Solution:
 2    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
 3        def build(low, high):
 4            if low > high:
 5                return None
 6            mid = (low + high) // 2
 7            node = TreeNode(nums[mid])
 8            node.left = build(low, mid - 1)
 9            node.right = build(mid + 1, high)
10            return node
11
12        return build(0, len(nums) - 1)

复杂度：

时间 O(n)
空间 O(log n)（递归栈，结果树不计）

6 路径累积和回溯

6.1 路径总和 | Easy

题目: 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

思路分析: 不要在递归里累加求和，而是做减法：每往下走一层，就从目标里减掉当前节点的值。到叶子节点时，只要剩余目标恰好等于叶子的值，这条路径就成立

递归定义：hasPathSum(node, rest) 表示"以 node 为根，能否凑出和为 rest 的根到叶路径"

node 为空 → False
node 是叶子 → rest == node.val
否则 → 左右子树任一满足 hasPathSum(child, rest - node.val) 即可

踩坑记录:

空树返回 False，不是 targetSum == 0。空树里没有任何根到叶的路径。

代码:

 1class Solution:
 2    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
 3        if not root:
 4            return False
 5        # 叶子节点：left 和 right 都为空才算
 6        if not root.left and not root.right:
 7            return targetSum == root.val
 8        rest = targetSum - root.val
 9        return (self.hasPathSum(root.left, rest)
10                or self.hasPathSum(root.right, rest))

复杂度:

时间 $O(n)$：每个节点最多访问一次
空间 $O(h)$：递归栈，最坏（链状树）$O(n)$

6.2 路径总和 II | Medium

题目: 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

思路分析: 从"判断有无"升级成"找出所有"，就必须记录路径，引入回溯模板：

进入节点  →  path.append(值)
              ↓
命中条件  →  res.append(path[:])   ← 存快照，必须拷贝
              ↓
          递归左右子树
              ↓
离开节点  →  path.pop()            ← 恢复现场

path 是整个递归过程中共享的可变列表，像栈一样随 DFS 深入和回退不断变化 踩坑记录:

path[:] 的拷贝不能省。直接 res.append(path) 存的是引用，path 后面还会被 pop，最终 res 里全是空列表。等价写法：list(path) / path.copy()
path.pop() 必须无条件执行

代码:

 1class Solution:
 2    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
 3        res, path = [], []
 4
 5        def dfs(node, rest):
 6            if not node:
 7                return
 8            path.append(node.val)          # 进入：入栈
 9            rest -= node.val
10            if not node.left and not node.right and rest == 0:
11                res.append(path[:])        # 命中：存快照，必须拷贝
12            dfs(node.left, rest)
13            dfs(node.right, rest)
14            path.pop()                     # 离开：出栈，恢复现场
15
16        dfs(root, targetSum)
17        return res

复杂度:

时间 $O(n^2)$：遍历是 $O(n)$，但每次命中要拷贝一条长度可达 $O(n)$ 的路径，最坏有 $O(n)$ 条路径命中
空间 $O(h)$：递归栈 + path（不计返回结果）

6.3 路径总和 III | Meidum

题目: 给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

思路分析: 与 LC 560 的唯一区别：数组是一条线，树是分叉的，所以离开节点时要把自己的贡献撤销。

踩坑记录:

回溯 cnt[cur] -= 1 不能忘。哈希表记录的是当前这条链上的前缀和，不是整棵树的。离开节点后必须撤销，否则左子树的前缀和会污染右子树，答案偏大

代码:

 1class Solution:
 2    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
 3        cnt = defaultdict(int)
 4        cnt[0] = 1
 5        def dfs(node, prefix):
 6            if not node:
 7                return 0
 8            prefix += node.val
 9            ans = cnt[prefix - targetSum]
10            cnt[prefix] += 1
11            ans += dfs(node.right, prefix) + dfs(node.left, prefix)
12            cnt[prefix] -= 1
13            return ans
14        return dfs(root, 0)
15

复杂度:

时间O(n)
空间O(n)

7 prev建立相邻关系

7.1 验证二叉搜索树 | Meidum

题目: 判断一棵树是否是合法 BST。有效二叉搜索树定义如下：

节点的左子树只包含 严格小于 当前节点的数。
节点的右子树只包含 严格大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树

思路分析：

踩坑记录：

区间必须是开区间（严格小于/大于），等于也不合法
初始边界用 float('-inf'), float('inf')，别假设节点值范围

代码：

plan 1: 上下界

1class Solution:
2    def isValidBST(self, root: Optional[TreeNode]) -> bool:
3        def valid(node, low, high):
4            if not node:
5                return True
6            if not (low < node.val < high):
7                return False
8            return valid(node.left, low, node.val) and valid(node.right, node.val, high)
9        return valid(root, float("-inf"), float("inf"))

plan 2: 中序遍历检查

 1class Solution:
 2    def isValidBST(self, root: Optional[TreeNode]) -> bool:
 3        self.prev = float("-inf")
 4        def dfs(node):
 5            if not node:
 6                return True
 7            if not dfs(node.left):
 8                return False
 9            if node.val <= self.prev:
10                return False
11            self.prev = node.val
12            return dfs(node.right)
13        return dfs(root)

 1class Solution:
 2    def isValidBST(self, root: Optional[TreeNode]) -> bool:
 3        # 哨兵:记录"中序序列里上一个访问过的节点值"
 4        # 初始为 -inf,保证第一个节点(即整棵树的最小值)必然通过检查
 5        self.prev = float("-inf")
 6
 7        def dfs(node):
 8            # 空节点没有值可检查,视为合法,直接向上返回 True
 9            if not node:
10                return True
11
12            # ① 左:先把整棵左子树中序遍历完
13            #    返回后 self.prev 已被更新成"左子树中最大的那个值"
14            #    左子树若已发现违规,这里短路上抛,不再往下走
15            if not dfs(node.left):
16                return False
17
18            # ② 根:轮到检查node自己
19            if node.val <= self.prev:
20                return False
21
22            # 检查通过,node成为下一个节点的"前驱"
23            self.prev = node.val
24
25            # ③ 右:遍历右子树,它的结果就是整棵子树的结论
26            return dfs(node.right)
27
28        return dfs(root)

复杂度：

时间 O(n)
空间 O(h)

7.2 二叉树展开为链表 | Medium

题目: 原地把二叉树展开成"只用 right 指针的链表"，顺序 = 前序遍历

思路分析：递归：站在 root 上：假设左右子树已经各自拉平成两条链，现在要做的是：① 把左链插到 root 和右链之间；② root.left 置空。插入时需要找到左链的末端（一路向右走到底）再接右链

迭代：从根开始迭代，对每个有左孩子的节点，找到其左子树的最右节点（它是前序里左子树最后被访问的），把原右子树挂到它的 right 上，再把左子树整体搬到右边

踩坑记录：

忘记 root.left = None，输出的"链表"里残留左指针，判错
找左链末端时走成 while p.left，应该是 while p.right（链表全在 right 上）

代码： plan 1: 递归

 1class Solution:
 2    def flatten(self, root: Optional[TreeNode]) -> None:
 3        prev = None
 4        def dfs(node):
 5            nonlocal prev
 6            if not node:
 7                return 
 8            dfs(node.right)
 9            dfs(node.left)
10            node.right = prev
11            node.left = None
12            prev = node
13        dfs(root)

plan 2: 迭代

 1class Solution:
 2    def flatten(self, root: Optional[TreeNode]) -> None:
 3        """
 4        Do not return anything, modify root in-place instead.
 5        """
 6        cur = root
 7        while cur:
 8            if cur.left:
 9                pre = cur.left
10                while pre.right:
11                    pre = pre.right
12                pre.right = cur.right
13                cur.right = cur.left
14                cur.left = None
15            cur = cur.right

复杂度：递归：

时间：O(n)
空间：O(h) ~ O(n) 迭代：
时间：O(n)
空间：O(1)

0 Basic#

1 层序遍历模板#

2 中序遍历模板#

3 二叉树的深度和直径#

4 二叉树的左右递归处理#

5 序列和树的重构#

6 路径累积和回溯#

7 prev建立相邻关系#

0 Basic

1 层序遍历模板

2 中序遍历模板

3 二叉树的深度和直径

4 二叉树的左右递归处理

5 序列和树的重构

6 路径累积和回溯

7 prev建立相邻关系