二叉树
二叉树的理论基础¶
二叉树的种类 在我们解题过程中二叉树有两种主要的形式：满二叉树和完全二叉树。
满二叉树 满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。
如图所示：
这棵二叉树为满二叉树，也可以说深度为k，有2^k-1个节点的二叉树。
完全二叉树 什么是完全二叉树？
完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（h从1开始），则该层包含 1~ 2^(h-1) 个节点。
大家要自己看完全二叉树的定义，很多同学对完全二叉树其实不是真正的懂了。
我来举一个典型的例子如题：
相信不少同学最后一个二叉树是不是完全二叉树都中招了。
之前我们刚刚讲过优先级队列其实是一个堆，堆就是一棵完全二叉树，同时保证父子节点的顺序关系。
二叉搜索树
前面介绍的树，都没有数值的，而二叉搜索树是有数值的了，二叉搜索树是一个有序树。
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉排序树
下面这两棵树都是搜索树
平衡二叉搜索树是在满足二叉搜索树有序性的基础上，进一步要求任意节点的左右子树高度差不超过 1（或在工程实现中保持近似平衡），从而将整棵树的高度控制在 O(log n)。这样可以避免普通二叉搜索树在极端情况下退化为链表，使查找、插入和删除在最坏情况下仍能保持对数级时间复杂度。 如图：
最后一棵 不是平衡二叉树，因为它的左右两个子树的高度差的绝对值超过了1。
C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作时间时间复杂度是logn，注意我这里没有说unordered_map、unordered_set，unordered_map、unordered_set底层实现是哈希表。
所以大家使用自己熟悉的编程语言写算法，一定要知道常用的容器底层都是如何实现的，最基本的就是map、set等等，否则自己写的代码，自己对其性能分析都分析不清楚！
二叉树的存储方式 二叉树可以链式存储，也可以顺序存储。
那么链式存储方式就用指针， 顺序存储的方式就是用数组。
顾名思义就是顺序存储的元素在内存是连续分布的，而链式存储则是通过指针把分布在各个地址的节点串联一起。
链式存储如图：
链式存储是大家很熟悉的一种方式，那么我们来看看如何顺序存储呢？
其实就是用数组来存储二叉树，顺序存储的方式如图：
用数组来存储二叉树如何遍历的呢？
如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。
但是用链式表示的二叉树，更有利于我们理解，所以一般我们都是用链式存储二叉树。
所以大家要了解，用数组依然可以表示二叉树。
二叉树的遍历方式
关于二叉树的遍历方式，要知道二叉树遍历的基本方式都有哪些。
一些同学用做了很多二叉树的题目了，可能知道前中后序遍历，可能知道层序遍历，但是却没有框架。
我这里把二叉树的几种遍历方式列出来，大家就可以一一串起来了。
二叉树主要有两种遍历方式：
深度优先遍历：先往深走，遇到叶子节点再往回走。
广度优先遍历：一层一层的去遍历。
这两种遍历是图论中最基本的两种遍历方式，后面在介绍图论的时候 还会介绍到。
那么从深度优先遍历和广度优先遍历进一步拓展，才有如下遍历方式：
深度优先遍历
- 1.前序遍历（递归法，迭代法）
- 2.中序遍历（递归法，迭代法）
- 3.后序遍历（递归法，迭代法）
广度优先遍历
- 层次遍历（迭代法）
在深度优先遍历中：有三个顺序，前中后序遍历， 有同学总分不清这三个顺序，经常搞混，我这里教大家一个技巧。
这里前中后，其实指的就是中间节点的遍历顺序，只要大家记住 前中后序指的就是中间节点的位置就可以了。
看如下中间节点的顺序，就可以发现，中间节点的顺序就是所谓的遍历方式，中间节点也就是正在处理的那一个节点（root）
前序遍历：中 左子树 右子树 中序遍历：左子树 中 右子树 后序遍历：左子树 右子树 中 大家可以对着如下图，看看自己理解的前后中序有没有问题。
最后再说一说二叉树中深度优先和广度优先遍历实现方式，我们做二叉树相关题目，经常会使用递归的方式来实现深度优先遍历，也就是实现前中后序遍历，使用递归是比较方便的。
之前我们讲栈与队列的时候，就说过栈其实就是递归的一种实现结构，也就说前中后序遍历的逻辑其实都是可以借助栈使用递归的方式来实现的。
而广度优先遍历的实现一般使用队列来实现，这也是队列先进先出的特点所决定的，因为需要先进先出的结构，才能一层一层的来遍历二叉树。
这里其实我们又了解了栈与队列的一个应用场景了。
具体的实现我们后面都会讲的，这里大家先要清楚这些理论基础。
二叉树的定义 刚刚我们说过了二叉树有两种存储方式顺序存储，和链式存储，顺序存储就是用数组来存，这个定义没啥可说的，我们来看看链式存储的二叉树节点的定义方式。
C++代码如下：
struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; 大家会发现二叉树的定义 和链表是差不多的，相对于链表 ，二叉树的节点里多了一个指针， 有两个指针，指向左右孩子。
这里要提醒大家要注意二叉树节点定义的书写方式。
在现场面试的时候 面试官可能要求手写代码，所以数据结构的定义以及简单逻辑的代码一定要锻炼白纸写出来。
因为我们在刷leetcode的时候，节点的定义默认都定义好了，真到面试的时候，需要自己写节点定义的时候，有时候会一脸懵逼！
总结 二叉树是一种基础数据结构，在算法面试中都是常客，也是众多数据结构的基石。
本篇我们介绍了二叉树的种类、存储方式、遍历方式以及定义，比较全面的介绍了二叉树各个方面的重点，帮助大家扫一遍基础。
说到二叉树，就不得不说递归，很多同学对递归都是又熟悉又陌生，递归的代码一般很简短，但每次都是一看就会，一写就废。
递归理解
理解递归的关键，不在于“函数怎么跳来跳去”，而在于明确两个阶段：向下递进构造问题，向上回溯汇总结果。思考时应按以下顺序进行：第一，先定义清楚递归函数的含义——它接收什么参数，返回什么结果；第二，确定终止条件——在什么情况下问题规模已经小到可以直接得到答案；第三，假设子问题已经被正确解决，思考当前层如何利用子问题的结果完成自身任务。执行时，调用栈会不断“向下”展开，直到触达终止条件；随后开始“出栈”，每一层利用下层返回值完成计算。这种“递进—触底—回溯”的结构，是所有递归的本质框架。掌握这一点后，不再关注代码的执行顺序，而是关注：当前函数在整棵递归树中的语义角色是什么。
94. 二叉树的中序遍历¶
给定一个二叉树的根节点 root ，返回它的中序遍历,输出一个数组
核心思路：递归
递归两个字要分开来看，”递“是一部分，说的是你这个函数调用自身的那个传递过程，”归“是指函数触发特定条件后停止调用自身并把返回值一层层地往回传的过程。 递归完之后才能得到想要的结果。
用“调用栈变化”这一条主线来理解整个过程。
当程序执行 dfs(1) 时，栈中压入一层 dfs(1)；接着执行 dfs(2)，栈变为 dfs(1) → dfs(2)；再执行 dfs(4)，栈变为 dfs(1) → dfs(2) → dfs(4)。此时在 dfs(4) 内部，先调用 dfs(4.left)，因为是 None，这一层调用立即返回，相当于短暂压栈又立刻弹栈。随后执行 res.append(4)，再调用 dfs(4.right)，同样因为是 None，立刻返回。到这里，dfs(4) 这一层函数的三条语句已经全部执行完毕，没有剩余代码，因此整层 dfs(4) 从调用栈弹出。栈状态回到 dfs(1) → dfs(2)，控制权自然回到 dfs(2) 中当初调用 dfs(2.left) 那一行的下一条语句，即执行 res.append(2)。整个过程不是“重新执行 dfs(4)”，而是“dfs(4) 执行完毕后弹栈，继续执行上一层尚未完成的代码”。这就是递归中所谓的“回溯”本质：函数执行结束即弹栈，程序从调用点之后继续向下执行。
from typing import Optional, List
class TreeNode:
def __init__(self, val = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
def dfs(node: Optional[TreeNode]):
# 递归终止条件
# 当前这一次 dfs(None) 调用结束后，return 表示当前left分支结束或者right分支结束，然后程序会回到父节点，
# 继续执行父节点没有执行完的代码，直到所有子树都被遍历完
if not node:
return
# 1. 先遍历左子树
dfs(node.left)
# 2. 访问当前节点
res.append(node.val)
# 3. 再遍历右子树
dfs(node.right)
dfs(root)
return res
# ---------- 测试 ----------
# 构造树
# root = [1, null, 2, 3]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
# 调用
sol = Solution()
print(sol.inorderTraversal(root))
[4, 2, 5, 1, 6, 3, 7]
时间复杂度
每个节点访问一次：
时间复杂度：O(n)
n 为节点数量。
空间复杂度
递归栈深度取决于树的高度。
最坏情况（链表形态）：
O(h)
平均情况（平衡树）：
O(log h)
前序遍历（中 → 左 → 右）¶
核心思想： 先访问当前节点，再递归左子树和右子树。
from typing import Optional, List
class TreeNode:
def __init__(self, val = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
def dfs(node: Optional[TreeNode]):
if not node:
return
# 1. 先访问当前节点
res.append(node.val)
# 2. 再遍历左子树
dfs(node.left)
# 3. 最后遍历右子树
dfs(node.right)
dfs(root)
return res
后序遍历（左 → 右 → 中）¶
核心思想： 先递归左右子树，最后访问当前节点。
from typing import Optional, List
class TreeNode:
def __init__(self, val = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
def dfs(node: Optional[TreeNode]):
if not node:
return
# 1. 先遍历左子树
dfs(node.left)
# 2. 再遍历右子树
dfs(node.right)
# 3. 最后访问当前节点
res.append(node.val)
dfs(root)
return res
104. 二叉树的最大深度¶
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
核心思路：树的最大深度 = 1 + max(左子树深度, 右子树深度)
对于任意一个节点 node：
如果 node 为空，深度为 0
否则：
当前节点的深度 = 1（当前节点本身）
max(左子树最大深度, 右子树最大深度)
递归天然适配树结构，因为：
每个子树本身也是一棵树。
执行逻辑本质
递归会一直往下走，直到遇到 None 返回 0。
然后从最底层开始回溯：
叶子节点返回 1
其父节点返回 2
一层一层往上累加
这叫“后序位置处理”—— 因为你必须先知道左右子树的高度，才能计算当前高度。
from typing import Optional
class TreeNode:
def __init__(self, val = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
# 递归终止条件
# 如果节点为空，说明到达叶子节点的下一层
if not root:
return 0
# 递归计算左子树的最大深度
left_depth = self.maxDepth(root.left)
# 递归计算右子树的最大深度
right_depth = self.maxDepth(root.right)
# 当前节点的深度 = 1 + 左右子树深度的较大值
return 1 + max(left_depth, right_depth)
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.left.left = TreeNode(None)
root.left.right = TreeNode(None)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(Solution().maxDepth(root))
3
时间复杂度
每个节点访问一次：
时间复杂度：O(n)
n 为节点数量。
空间复杂度
取决于递归栈深度：
最坏情况（链表形态）：
O(n)
平均情况（平衡树）：
O(log n)
226. 翻转二叉树¶
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
核心思路：
这是一道很经典的二叉树问题。显然，我们从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转。如果当前遍历到的节点 root 的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，即可完成以 root 为根节点的整棵子树的翻转。
from typing import Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return
left = self.invertTree(root.left)
right = self.invertTree(root.right)
root.left, root.right = right, left
return root
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.left = TreeNode(6)
root.right.right = TreeNode(9)
Solution().invertTree(root)
print(root.val, root.left.val, root.right.val, root.left.left.val, root.left.right.val, root.right.left.val, root.right.right.val)
4 7 2 9 6 3 1
时间复杂度：O(N)，其中 N 为二叉树节点的数目。我们会遍历二叉树中的每一个节点，对每个节点而言，我们在常数时间内交换其两棵子树。
空间复杂度：O(N)。使用的空间由递归栈的深度决定，它等于当前节点在二叉树中的高度。在平均情况下，二叉树的高度与节点个数为对数关系，即 O(logN)。而在最坏情况下，树形成链状，空间复杂度为 O(N)。
101. 对称二叉树¶
给你一个二叉树的根节点 root ， 检查它是否轴对称。
核心本质： 一棵树是对称的 ⇔ 它的左子树和右子树是镜像关系。
所谓镜像关系，本质上是：
两个节点值相同
左节点的左子树 == 右节点的右子树
左节点的右子树 == 右节点的左子树
也就是“交叉对比”。
from typing import Optional
class TreeNode:
def __init__(self, val: int = 0, left: 'TreeNode|None' = None, right: 'TreeNode|None' = None):
self.val = val
self.left = left
self.right = right
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
# 空树本身是对称的
if not root:
return True
# 判断两棵子树是否互为镜像
def is_mirror(t1, t2):
# 情况1：两个都为空
if not t1 and not t2:
return True
# 情况2：一个为空一个不为空
if (t1 is None) != (t2 is None):
return False
# 情况3：当前节点值不同
if t1.val != t2.val:
return False
# 核心：交叉比较; 先不断递进 is_mirror(t1.left, t2.right)，一路走到最底层, 回溯到当前层, 再递进 is_mirror(t1.right, t2.left)
return (is_mirror(t1.left, t2.right) and is_mirror(t1.right, t2.left))
return is_mirror(root.left, root.right)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(2)
root.left.left = TreeNode(3)
root.left.right = TreeNode(4)
root.right.left = TreeNode(4)
root.right.right = TreeNode(3)
print(Solution().isSymmetric(root))
True
时间复杂度：O(n); 每个节点最多访问一次。
空间复杂度：O(N);使用的空间由递归栈的深度决定，它等于当前节点在二叉树中的高度。在平均情况下，二叉树的高度与节点个数为对数关系，即 O(logN)。而在最坏情况下，树形成链状，空间复杂度为 O(N)。
543. 二叉树的直径¶
给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
核心思路：
这是一个典型的“后序递归 + 全局更新”的问题。
因为你必须先知道左右子树的最大深度， 才能计算当前节点的“路径长度”。
本质理解：
一条最长路径（直径）一定经过某个节点，并且等于：左子树最大深度 + 右子树最大深度
from typing import Optional
class TreeNode:
def __init__(self, val: int = 0, left: 'TreeNode|None' = None, right: 'TreeNode|None' = None):
self.val = val
self.left = left
self.right = right
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
self.max_diameter = 0
def depth(node: Optional[TreeNode]) -> int:
"""递归函数只负责一件事：返回当前节点的最大深度
在递归过程中顺便更新答案"""
# 空节点深度为 0
if not node:
return 0
# 1. 递归计算左右子树深度
left_depth = depth(node.left)
right_depth = depth(node.right)
# 2. 更新当前节点作为“拐点”时的最大路径
# 路径长度 = 左深度 + 右深度
self.max_diameter = max(self.max_diameter, left_depth + right_depth)
# 3. 返回当前节点的最大深度
return max(left_depth, right_depth) + 1
depth(root)
return self.max_diameter
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(Solution().diameterOfBinaryTree(root))
3
时间复杂度： O(n) 每个节点访问一次。
空间复杂度： O(h) 递归栈深度等于树高。 最坏 O(n)，平均 O(log n)。
队列的数据结构¶
一、队列（Queue）的本质
队列是一种线性数据结构，遵循 FIFO（First In First Out，先进先出）原则。
核心特征：
- 插入发生在尾部（enqueue）
- 删除发生在头部（dequeue）
- 不支持随机访问（不同于数组）
抽象模型：
头部 ← 出队 ← [元素1, 元素2, 元素3] ← 入队 ← 尾部
在算法中常用于：
- 广度优先搜索（BFS）
- 层序遍历
- 生产者-消费者模型
- 滑动窗口问题
——————————————
二、Python 中的队列实现方式
1）list 实现队列（不推荐）
queue = []
queue.append(x) # 入队
queue.pop(0) # 出队
问题：
pop(0) 时间复杂度 O(n)，因为需要整体左移。
因此 list 不适合作为真正意义上的队列。
——————————————
2）collections.deque（推荐）
deque（double-ended queue，双端队列）是 Python 内置的高效队列结构。
from collections import deque
queue = deque()
queue.append(x) # 右侧入队
queue.popleft() # 左侧出队
deque 底层结构： 双向链表 + 分块数组结构（不是简单 list）
特点：
- 两端插入删除都是 O(1)
- 不支持高效随机访问
——————————————
三、deque 常用操作与复杂度
创建：
deque()
deque([1,2,3])
时间复杂度：O(n)
入队操作：
append(x) # 右侧插入
appendleft(x) # 左侧插入
时间复杂度：O(1)
出队操作：
pop() # 右侧弹出
popleft() # 左侧弹出
时间复杂度：O(1)
访问元素：
queue[0]
queue[-1]
时间复杂度：O(1)
随机访问中间元素：
queue[i]
时间复杂度：O(n)
长度：
len(queue)
时间复杂度：O(1)
——————————————
四、deque vs list 复杂度对比
| 操作 | list | deque |
|---|---|---|
| append | O(1) | O(1) |
| pop() | O(1) | O(1) |
| pop(0) | O(n) | O(1) |
| popleft() | 不支持 | O(1) |
| 随机访问 | O(1) | O(n) |
核心差异： list 擅长尾部操作和随机访问。 deque 擅长两端操作。
——————————————
五、算法场景中的选择原则
使用 deque 当：
- 需要频繁头部删除
- 需要 BFS
- 需要滑动窗口
- 需要单调队列
使用 list 当：
- 需要频繁随机访问
- 只在尾部操作
——————————————
六、空间复杂度分析
deque 的空间复杂度：O(n)
它会为每个元素维护双向指针和块结构开销， 但总体仍为线性空间。
——————————————
七、总结核心
队列的本质是“顺序消费”。 在 Python 中：
- list 不是严格意义的队列
- deque 是标准、高效队列实现
- BFS 必须使用 deque
- 时间复杂度优势体现在 popleft() 为 O(1)
102. 二叉树的层序遍历¶
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
核心思路:
这是一个标准的 广度优先搜索（BFS） 问题。
核心本质： 层序遍历就是“按层推进”。 而“按层推进”的天然结构就是 队列（先进先出）。
思维模型：
队列里存放“当前层的节点”
每一轮循环，处理当前层所有节点
同时把下一层节点加入队列
from typing import Optional, List
from collections import deque
class TreeNode:
def __init__(self, val: int = 0, left: 'TreeNode|None' = None, right: 'TreeNode|None' = None):
self.val = val
self.left = left
self.right = right
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue) # 当前层节点数量
current_level = []
for _ in range(level_size):
node = queue.popleft()
current_level.append(node.val)
# 将下一层加入队列
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(current_level)
return result
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(Solution().levelOrder(root))
[[3], [9, 20], [15, 7]]
时间复杂度： O(n); 每个节点入队、出队各一次。
空间复杂度： O(n); 最坏情况下队列中会存储一整层节点（完全二叉树最后一层）。
108. 将有序数组转换为二叉搜索树¶
给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵 平衡 二叉搜索树。
二叉搜索树（BST）是一种满足有序约束的二叉树结构：对于任意节点，其左子树中所有节点的值都小于该节点的值，右子树中所有节点的值都大于该节点的值，并且左右子树本身也必须是二叉搜索树。这种结构保证了中序遍历结果是递增序列，从而使查找、插入、删除操作在平均情况下具有较高效率。
平衡二叉搜索树是在满足二叉搜索树有序性的基础上，进一步要求任意节点的左右子树高度差不超过 1（或在工程实现中保持近似平衡），从而将整棵树的高度控制在 O(log n)。这样可以避免普通二叉搜索树在极端情况下退化为链表，使查找、插入和删除在最坏情况下仍能保持对数级时间复杂度。 。
核心思路：
这是一个典型的“构造平衡 BST”的问题。
核心本质：
有序数组 + 平衡 BST
BST 的性质： 左 < 根 < 右
平衡的本质： 左右子树高度尽量接近。
关键思路
有序数组已经排好序。
要满足：
中间元素作为根节点
左半部分构建左子树
右半部分构建右子树
这样天然保证：
BST 有序性成立
左右规模接近 → 树高度平衡
这就是“分治思想”。
from typing import Optional, List
class TreeNode:
def __init__(self, val: int = 0, left: 'TreeNode|None' = None, right: 'TreeNode|None' = None):
self.val = val
self.left = left
self.right = right
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
def build(left: int, right: int) -> Optional[TreeNode]:
# 递归终止条件
if left > right:
return None
# 选择中点作为根节点
mid = (left + right) // 2
root = TreeNode(nums[mid])
# 递归构建左右子树
root.left = build(left, mid - 1)
root.right = build(mid + 1, right)
return root
return build(0, len(nums) - 1)
nums = [-10, -3, 0, 5, 9]
bst_root = Solution().sortedArrayToBST(nums)
时间复杂度 O(n)
每个元素只会被创建成节点一次。
空间复杂度 O(log n)
递归深度等于树高。 因为是平衡树，树高为 O(log n)。
98. 验证二叉搜索树¶
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 严格小于 当前节点的数。 节点的右子树只包含 严格大于 当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。
核心思想：
区间递归
每个节点都必须落在一个合法区间 (low, high) 内。
初始时： 整棵树的根节点合法区间为 (-∞, +∞) 递归规则：
- 左子树：上界变成当前节点值
- 右子树：下界变成当前节点值
这样可以保证： 每个节点都同时受到“所有祖先节点”的约束
from typing import Optional
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val: int = 0, left: 'TreeNode|None' = None, right: 'TreeNode|None' = None):
self.val = val
self.left = left
self.right = right
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def dfs(node: Optional[TreeNode], lower: float, upper: float) -> bool:
"""
函数含义：
判断以 node 为根的子树，是否满足：
所有节点值都在 (lower, upper) 区间内。
返回值：
True -> 该子树是合法 BST
False -> 该子树不是合法 BST
"""
# 1. 空节点天然合法
if node is None:
return True
# 2. 当前节点必须满足区间限制
if node.val <= lower or node.val >= upper:
return False
# 3. 左子树必须全部 < node.val
# 4. 右子树必须全部 > node.val
left_valid = dfs(node.left, lower, node.val)
right_valid = dfs(node.right, node.val, upper)
# 当前子树是否合法 = 左子树合法 且 右子树合法
return left_valid and right_valid
# 初始时根节点没有边界限制
return dfs(root, float("-inf"), float("inf"))
root = TreeNode(2)
root.left = TreeNode(1)
root.right = TreeNode(3)
print(Solution().isValidBST(root)) # True
True
时间复杂度：O(n); 每个节点访问一次。
空间复杂度：O(h); 递归栈深度，最坏 O(n)，平均 O(log n)。
230. 二叉搜索树中第 K 小的元素¶
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（k 从 1 开始计数）。
核心思路:
对 BST 进行中序遍历（左 → 根 → 右）时，得到的节点序列是严格递增的。因此，第 k 小的元素，等价于中序遍历过程中访问到的第 k 个节点。算法通过递归实现中序遍历，并用 self.count 记录当前已经访问的节点数量；每访问一个节点计数加一，当计数等于 k 时，将当前节点值保存为结果。为了避免不必要的遍历，在找到结果后通过判断 self.result is not None 进行剪枝，使递归提前终止。整体本质是：把“第 k 小”问题转化为“中序遍历的第 k 个访问节点”问题，并通过计数器精确定位目标元素。
from typing import Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
# 用于记录已经访问的节点数量
self.count = 0
# 用于保存最终答案
self.result = None
def inorder(node: Optional[TreeNode]):
"""
中序遍历函数
遍历顺序：左 -> 根 -> 右
BST 的中序遍历是递增序列
"""
if not node:
return
# 1️⃣ 递归遍历左子树（更小的元素）
inorder(node.left)
# 如果已经找到答案，直接return剪枝
""""当执行到 return 时：
当前函数调用结束
当前函数帧从栈中弹出
控制权回到“调用它的那一行代码”"""
if self.result is not None:
return
# 2️⃣ 访问当前节点
self.count += 1
# 当访问到第 k 个节点时，记录答案并剪枝
if self.count == k:
self.result = node.val
return
# 3️⃣ 递归遍历右子树（更大的元素）
inorder(node.right)
inorder(root)
return self.result
root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(5)
root.left.right = TreeNode(2)
root.right.left = TreeNode(4)
print(Solution().kthSmallest(root, 3)) # 输出 3
3
时间复杂度：O(H+k)，其中 H 是树的高度。在开始遍历之前，我们需要 O(H) 到达叶结点,这一步最多走 H 层。 因此，初始阶段耗时 O(H)。 第二部分：访问前 k 个节点 中序遍历是递增序列。 找到第 k 小元素，需要访问前 k 个节点。 这部分耗时 O(k)。 合在一起： 时间复杂度 = O(H + k)。
当树是平衡树时， 平衡树的高度为 H ≈ log N； 时间复杂度取得最小值 O(logN+k)；
当树是线性树（树中每个结点都只有一个子结点或没有子结点）时，这时高度： H = N。时间复杂度取得最大值 O(N+k)。
空间复杂度：O(H)，栈中最多需要存储 H 个元素。当树是平衡树时，空间复杂度取得最小值 O(logN)；
当树是线性树时，空间复杂度取得最大值 O(N)。
199. 二叉树的右视图¶
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
核心思路：
这道题的本质是：每一层只取最右边的那个节点。 因此主要逻辑是“按层遍历（二叉树层序遍历）（广度优先搜索BFS）”，然后记录每一层的最后一个节点。
from typing import Optional, List
from collections import deque
class TreeNode:
def __init__(self, val: int = 0, left: 'TreeNode|None' = None, right: 'TreeNode|None' = None):
self.val = val
self.left = left
self.right = right
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
# 如果树为空
if not root:
return []
result = []
queue = deque([root])
# 层序遍历
while queue:
size = len(queue) # 当前层的节点数量
for i in range(size):
node = queue.popleft()
# 如果是当前层最后一个节点
if i == size - 1:
result.append(node.val)
# 先加入左子节点
if node.left:
queue.append(node.left)
# 再加入右子节点
if node.right:
queue.append(node.right)
return result
设节点总数为 n。
时间复杂度： O(n) 每个节点只访问一次。
空间复杂度应当从运行过程中同时占用的最大辅助空间来分析。语句 queue = deque([root]) 仅创建了一个包含 1 个元素的双端队列，其初始化时间复杂度为 O(1)，空间复杂度也为 O(1)，因为只是分配常数级空间存放根节点。真正影响空间复杂度的是后续层序遍历过程中队列的增长情况：在完全二叉树中，某一层可能同时存在约 n/2 个节点，队列会膨胀到 O(n) 规模；而在链状树中队列始终为 O(1)，但结果数组会达到 O(n)。因此总体空间复杂度为 O(n)，不是因为队列初始化语句，而是因为在最坏结构下队列或结果数组会达到线性规模。
114. 二叉树展开为链表¶
给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。 展开后的单链表应该与二叉树 先序遍历 顺序相同。
核心思路：
通过逆先序遍历（右 → 左 → 根），利用一个全局指针从后往前构建链表，使最终 right 指针顺序等于先序遍历顺序，并将所有 left 指针清空。
from typing import Optional
class TreeNode:
def __init__(self, val: int = 0, left: 'TreeNode|None' = None, right: 'TreeNode|None' = None):
self.val = val
self.left = left
self.right = right
class Solution:
def flatten(self, root: Optional[TreeNode]) -> None:
self.prev = None
def dfs(node: Optional[TreeNode]) -> None:
if not node:
return
# 先递归右子树
dfs(node.right)
# 再递归左子树
dfs(node.left)
# 重新连接指针, 当前节点右指针指向已经排好序的self.prev节点，左指针置空
node.right = self.prev
node.left = None
# 更新 prev
self.prev = node
dfs(root)
# ---------- 测试 ----------
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(5)
root.left.left = TreeNode(3)
root.left.right = TreeNode(4)
root.right.left = None
root.right.right = TreeNode(6)
Solution().flatten(root)
curr = root
while curr:
print(curr.val, end=" ")
curr = curr.right
1 2 3 4 5 6
时间复杂度 O(n)， 空间复杂度 O(h)，其中 h 为树高。
105. 从前序与中序遍历序列构造二叉树¶
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
核心思路：
利用先序遍历确定根节点，利用中序遍历划分左右子树。
一、核心规律（必须彻底理解）
1）先序遍历（根 → 左 → 右）
第一个元素一定是整棵树的根节点。
2）中序遍历（左 → 根 → 右）
根节点左边的部分是左子树
根节点右边的部分是右子树
因此构造流程是：
第一步： 从 preorder 取出当前子树的根。
第二步： 在 inorder 中找到这个根的位置。
第三步： 根据中序划分左右子树的范围。
第四步： 递归构造左右子树。
二、关键优化
如果每次在 inorder 里用 index 查找根的位置，会退化为 O(n²)。
优化方式：
提前建立一个哈希表：
value → index
这样查找是 O(1)。
from typing import Optional, List
class TreeNode:
def __init__(self, val: int = 0, left: 'TreeNode|None' = None, right: 'TreeNode|None' = None):
self.val = val
self.left = left
self.right = right
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
# --- 1. 建立中序数组的索引表，便于 O(1) 查找 ---
index_map = {}
for i, val in enumerate(inorder):
index_map[val] = i
# 使用一个指针记录当前处理到的 preorder 位置
self.pre_index = 0
# --- 2. 定义递归函数 ---
def helper(left: int, right: int) -> Optional[TreeNode]:
"""
构造 inorder[left:right] 这一段对应的子树
"""
# 如果区间无效，说明没有节点
if left > right:
return None
# --- 3. 先序遍历的第一个元素一定是根 ---
root_val = preorder[self.pre_index]
self.pre_index += 1
# 创建根节点
root = TreeNode(root_val)
# --- 4. 在中序遍历中找到根的位置 ---
mid = index_map[root_val]
# --- 5. 递归构造左子树 ---
root.left = helper(left, mid - 1)
# --- 6. 递归构造右子树 ---
root.right = helper(mid + 1, right)
return root
# 从整个区间开始构造
return helper(0, len(inorder) - 1)
preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]
root = Solution().buildTree(preorder, inorder)
# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
index_map = dict()
for i, val in enumerate(inorder):
index_map[val] = i
self.preorder_index = 0
def helper(left, right):
if left > right:
return None
root_val = preorder[self.preorder_index]
root = TreeNode(root_val)
self.preorder_index += 1
mid = index_map[root_val]
root.left = helper(left, mid - 1)
root.right = helper(mid + 1, right)
return root
return helper(0, len(preorder) - 1)
时间复杂度
设节点数为 n。
1）建立 index_map 遍历一次 inorder → O(n)
2）递归构造树 每个节点：
创建一次
查哈希表一次
进入递归一次
每个节点只被访问一次。
因此：
时间复杂度 = O(n)
空间复杂度
1）哈希表 index_map → O(n)
2）递归栈深度：
平衡二叉树 → O(log n)
退化为链 → O(n)
因此空间复杂度= O(n)
437. 路径总和 III¶
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
核心思路：
在一棵树中，统计所有向下路径（父 → 子）中，节点值之和等于 targetSum 的路径数量。
关键点：
不一定从根开始
不一定到叶子结束
但必须是“连续向下”的路径
这类问题的标准解法是：
前缀和 + DFS + 哈希表
这是一种树上的“路径和计数”技巧，本质等价于数组中的“子数组和等于 K”。
一、核心思想（必须彻底理解）
设当前遍历到某个节点时：
当前路径和为：
current_sum
如果存在一个“之前的前缀和”：
current_sum - prefix_sum = targetSum
那么：
prefix_sum = current_sum - targetSum
说明：
从那个前缀之后到当前节点这一段路径的和就是 targetSum。
因此我们用一个哈希表记录：
prefix_sum 出现的次数。
二、算法步骤
使用 DFS 遍历整棵树
维护 current_sum
每到一个节点：
先更新 current_sum
查询 current_sum - targetSum 在哈希表中的次数
累加到结果
然后把 current_sum 加入哈希表
递归左右子树
回溯时，把当前 prefix_sum 次数减 1（恢复现场）
from typing import Optional
from collections import defaultdict
class TreeNode:
def __init__(self, val: int = 0, left: 'TreeNode|None' = None, right: 'TreeNode|None' = None):
self.val = val
self.left = left
self.right = right
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
# prefix_count[x] 表示：
# 当前路径上，前缀和为 x 的出现次数
# defaultdict(int) 的作用，本质是访问一个“还不存在的键”时，自动返回默认值 0，defaultdict必须要进行设定，defaultdict[int]，默认返回0；defaultdict[list]，默认返回[]。
prefix_count = defaultdict(int)
# 为什么要初始化 prefix_count[0] = 1 ?
# 因为如果当前路径本身就等于 targetSum，
# 即 current_sum == targetSum，
# 那么 current_sum - targetSum = 0，
# 说明存在一条“从根开始”的路径。
prefix_count[0] = 1
# 用来记录满足条件的路径数量
self.result = 0
def dfs(node: Optional[TreeNode], current_sum: int):
# 如果节点为空，直接返回
if not node:
return
# -----------------------------
# 1️⃣ 进入当前节点：更新路径和
# -----------------------------
current_sum += node.val
# -----------------------------
# 2️⃣ 计算需要找的前缀和
# -----------------------------
# 我们想找：
# current_sum - prefix_sum = targetSum
# 所以 prefix_sum = current_sum - targetSum
need = current_sum - targetSum
# 如果以前的路径中出现过这种前缀和，
# 说明存在一条路径和为 targetSum
self.result += prefix_count[need]
# -----------------------------
# 3️⃣ 把当前前缀和加入哈希表
# -----------------------------
# 表示：当前节点加入路径
prefix_count[current_sum] += 1
# -----------------------------
# 4️⃣ 递归进入左右子树
# -----------------------------
dfs(node.left, current_sum)
dfs(node.right, current_sum)
# -----------------------------
# 5️⃣ 回溯（关键步骤）
# -----------------------------
# 离开当前节点时，
# 必须把当前前缀和移除，
# 因为这条路径不再属于“当前路径”
prefix_count[current_sum] -= 1
dfs(root, 0)
return self.result
from typing import Optional
from collections import defaultdict
class TreeNode:
def __init__(self, val: int = 0, left: 'TreeNode|None' = None, right: 'TreeNode|None' = None):
self.val = val
self.left = left
self.right = right
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
prefix_count = defaultdict(int)
prefix_count[0] = 1 # 空路径前缀
self.result = 0
def dfs(node: Optional[TreeNode], current_sum: int):
if not node:
return
# 更新当前路径和
current_sum += node.val
# 查找是否存在满足条件的前缀
need = current_sum - targetSum
self.result += prefix_count[need]
# 将当前前缀和加入哈希表
prefix_count[current_sum] += 1
# 递归左右子树
dfs(node.left, current_sum)
dfs(node.right, current_sum)
# 回溯：移除当前路径的前缀和
prefix_count[current_sum] -= 1
dfs(root, 0)
return self.result
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(-3)
root.left.left = TreeNode(3)
root.left.right = TreeNode(2)
root.right.right = TreeNode(11)
root.left.left.left = TreeNode(3)
root.left.left.right = TreeNode(-2)
root.left.right.right = TreeNode(1)
print(Solution().pathSum(root, 8)) # 输出 3
3
时间复杂度分析
每个节点：访问一次,查哈希 O(1),更新哈希 O(1)
因此： 时间复杂度 = O(n)
空间复杂度分析
1）哈希表最坏可能存 n 个不同前缀和 → O(n)
2）递归栈最坏 O(n)
总体空间复杂度： O(n)
236. 二叉树的最近公共祖先¶
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
核心思路:
这道题的本质是：在一棵普通二叉树中，寻找两个节点 p 和 q 的最低公共祖先（LCA）。由于不是二叉搜索树，不能利用大小关系，只能使用“后序遍历 + 递归回溯”的方式解决。
核心思想可以概括为一句话：
在每个节点处判断： p 和 q 是否分别出现在它的左右子树中，如果是，那么当前节点就是最近公共祖先。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
# ---------- 递归终止条件 ----------
# 1. 如果当前节点为空，说明这条路径没有找到 p 或 q
# 直接返回 None，表示“当前子树没有目标节点”
if not root:
return None
# 2. 如果当前节点本身就是 p 或 q
# 直接返回当前节点
# 注意：节点本身也可以是自己的祖先
if root == p or root == q:
return root
# ---------- 递归搜索左右子树 ----------
# 在左子树中查找 p 或 q
# left 的含义：
# - 如果左子树找到了 p 或 q，返回那个节点
# - 如果左子树中 p 和 q 都找到了，返回它们的 LCA
# - 如果都没找到，返回 None
left = self.lowestCommonAncestor(root.left, p, q)
# 在右子树中查找 p 或 q
# 含义与 left 相同
right = self.lowestCommonAncestor(root.right, p, q)
# ---------- 根据左右子树的返回结果判断当前节点 ----------
# 情况 1：左右子树都返回非空
# 说明：
# - p 在左子树
# - q 在右子树
# 或者相反
#
# 这说明当前节点是 p 和 q 第一次“分叉”的地方
# 因此当前节点就是最近公共祖先
if left and right:
return root
# 情况 2：只有一边非空
#
# 说明：
# - p 和 q 都在同一侧
# - 或者只找到了其中一个
#
# 此时当前节点不是 LCA
# 需要把找到的那个节点继续向上传递
#
# 如果 left 不为空，就返回 left
# 否则返回 right
return left if left else right
root = TreeNode(3)
root.left = TreeNode(5)
root.right = TreeNode(1)
root.left.left = TreeNode(6)
root.left.right = TreeNode(2)
root.right.left = TreeNode(0)
root.right.right = TreeNode(8)
root.left.right.left = TreeNode(7)
root.left.right.right = TreeNode(4)
print(Solution().lowestCommonAncestor(root, root.left, root.right.right).val) # 输出 3
3
class Solution:
def lowestCommonAncestor(self, root, p, q):
if not root:
return None
if root == p or root == q:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right:
return root
return left if left else right
root = TreeNode(3)
root.left = TreeNode(5)
root.right = TreeNode(1)
root.left.left = TreeNode(6)
root.left.right = TreeNode(2)
root.left.right.left = TreeNode(7)
root.left.right.right = TreeNode(4)
print(Solution().lowestCommonAncestor(root, root.left, root.left.right.right).val) # 输出 3
5
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
def dfs(node):
if not node:
return None
if node == p or node == q:
return node
left = dfs(node.left)
right = dfs(node.right)
if left and right:
return node
if left:
return left
if right:
return right
return None
return dfs(root)
root = TreeNode(3)
root.left = TreeNode(5)
root.right = TreeNode(1)
root.left.left = TreeNode(6)
root.left.right = TreeNode(2)
root.left.right.left = TreeNode(7)
root.left.right.right = TreeNode(4)
print(Solution().lowestCommonAncestor(root, root.left, root.left.right.right).val) # 输出 5
5
时间复杂度：O(n) 每个节点最多访问一次。
空间复杂度：O(h) h 是树高（递归栈深度）。
如果是平衡树，O(log n) 如果是链式结构，O(n)
124. 二叉树中的最大路径和¶
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
核心思路：
对于每一个节点，我们要计算两种值：
第一种：向父节点返回的最大贡献值 定义为： “从当前节点出发，向下走，只能选一条边，所能获得的最大路径和”
它必须是单边路径，因为如果同时选左右两边，就形成分叉，无法继续向上传递。
第二种：以当前节点为“拐点”的最大路径值 定义为：
left贡献 + 当前节点 + right贡献
这是一个完整路径，不能向上延伸，但可能是全局最大。
from typing import Optional
class TreeNode:
def __init__(self, val: int = 0, left: 'TreeNode|None' = None, right: 'TreeNode|None' = None):
self.val = val
self.left = left
self.right = right
class Solution:
def maxPathSum(self, root: Optional[TreeNode]) -> int:
# 全局最大路径和
# 必须初始化为负无穷，因为节点可能全为负数
self.max_sum = float('-inf')
def dfs(node):
# 如果节点为空
# 向上返回 0（表示没有贡献）
if not node:
return 0
# 递归计算左子树的最大单边路径和
left_gain = dfs(node.left)
# 递归计算右子树的最大单边路径和
right_gain = dfs(node.right)
# 如果子树贡献为负数，不如不要
# 因为加上负数会让路径变小
left_gain = max(left_gain, 0)
right_gain = max(right_gain, 0)
# 当前节点作为“最高点”的完整路径
# 左 + 当前 + 右
current_path_sum = node.val + left_gain + right_gain
# 更新全局最大路径和
self.max_sum = max(self.max_sum, current_path_sum)
# 返回给父节点的值只能是“单边路径”
# 因为路径不能分叉
return node.val + max(left_gain, right_gain)
dfs(root)
return self.max_sum
root = TreeNode(-10)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(Solution().maxPathSum(root)) # 输出 42
42
时间复杂度：O(n) 每个节点访问一次。
空间复杂度：O(h) 递归栈深度。