07-二叉树

基础知识

二叉树的遍历

前中后，是以根的顺序。

遍历方式	核心数据结构	适用场景
前序 `根`左右	栈 / 递归	树的克隆、序列化
中序左`根`右	栈 / 递归	BST 排序、验证 BST
后序左右`根`	栈 / 递归	垃圾回收、依赖处理、求树高度
层序	队列 (Queue)	寻找最短路径、按层打印

队列和栈

栈

先进 后出

队列

先进 先出

双端队列

两边 皆可出

python

from collections import deque

def demo_deque_basics():
    # 1. 初始化
    # 可以从列表、字符串或其他可迭代对象创建
    dq = deque([1, 2, 3])
    print(f"初始化 deque: {dq}")

    # 2. 右侧操作 (类似 list)
    dq.append(4)           # 添加到末尾
    last = dq.pop()        # 弹出末尾
    print(f"右侧操作后: {dq}, 弹出的值: {last}")

    # 3. 左侧操作 (deque 的杀手锏)
    dq.appendleft(0)       # 添加到开头
    first = dq.popleft()   # 弹出开头
    print(f"左侧操作后: {dq}, 弹出的值: {first}")

    # 4. 访问与长度
    print(f"队首元素: {dq[0]}, 队尾元素: {dq[-1]}, 长度: {len(dq)}")

def demo_deque_advanced():
    dq = deque([1, 2, 3, 4, 5])
    
    # 1. 旋转 (Rotate)
    # 正数：向右旋转；负数：向左旋转
    dq.rotate(1)  # [5, 1, 2, 3, 4]
    print(f"向右旋转 1 位: {dq}")
    dq.rotate(-2) # [2, 3, 4, 5, 1]
    print(f"向左旋转 2 位: {dq}")

    # 2. 限制最大长度 (常用作滑动窗口)
    # 当超过 maxlen 时，新元素加入会导致另一端元素自动弹出
    window = deque(maxlen=3)
    for i in range(5):
        window.append(i)
        print(f"添加 {i} 后的窗口: {list(window)}")

    # 3. 清空
    window.clear()
    print(f"清空后长度: {len(window)}")

if __name__ == "__main__":
    print("--- 基础功能测试 ---")
    demo_deque_basics()
    print("\n--- 进阶功能测试 ---")
    demo_deque_advanced()

题目总结

1-094-二叉树的中序遍历

leetcode-094

输入：二叉树根节点
输出：中序遍历结果，左-> 根 -> 右

DFS 中序遍历

递归终止：空节点则返回[]
递归遍历 左孩子
访问 根节点
递归遍历 右孩子

栈中序遍历

构建栈stack和curr=root
当curr不为空或栈不为空，执行循环
- curr往左走，左孩子入栈，到达最左
- 栈顶出栈 访问最左元素
- curr 转向右子树

1-114-二叉树的前序遍历

leetcode-114

根 -> 左 -> 右

栈前序遍历方法

构建栈，root先入栈
当栈不为空，执行循环
- 栈顶元素 出栈，访问根节点
- 右孩子 先入栈，后访问右孩子
- 左孩子 后入栈，先访问左孩子

1-145-二叉树的后序遍历

leetcode-145

后序遍历：左 -> 右 -> 根

后序 vs 先序

先序：根 -> 左 -> 右
后序：左 -> 右 -> 根 。
可先按照先序得 根 右左，翻转回 左右 根

栈先序翻转得后序法

先得 根 -> 右 -> 左，再反转回 左 -> 右 -> 根
构建栈，root先入栈
当栈不为空，执行循环
- 栈顶元素 出栈，访问 根节点
- 左孩子 先入栈，右孩子 再入栈
  - 先访问右孩子、再访问左孩子
得遍历结果 根 右左
把遍历结果 倒序则遍后序， 左右 根

2-104-二叉树的最大深度

leetcode-104

求根节点到叶子节点的最大长度

深度DFS 递归解法

递归终止：节点为空，返回0
递归计算： 左孩子深度、右孩子深度
1 + max(left_depth, right_depth)

队列层次遍历

构建队列deque，
循环每次处理1层，计算当前层size=len(queue)
访问当前节点时，叶子节点按左右依次入队。

BFS 计算深度

root 入队，while 队列不为空，做循环
- 根据队列长度获取当前层长度
- 循环出队n次，每出队一个节点，把左右孩子 依次入队
- 每层：深度 += 1

3-226-翻转二叉树

leetcode-226

翻转二叉树，左右节点 做交换。

DFS 翻转二叉树

递归终止条件：节点为空
递归翻转左孩子、递归翻转右孩子
翻转当前root的左右孩子

BFS 翻转二叉树

构建队列，root入队
队列有值做循环
- 当前node = 队首出队
- 交换 当前node的左右孩子
- 当前node的左右孩子 依次入队。仅不为空时才入队。

4-101-对称二叉树

leetcode-101

判断一棵树是否是对称二叉树，它的左子树和右子树是否互为镜像
- 左树的 左孩子 == 右树的 右孩子
- 左树的 右孩子 == 右树的 左孩子

DFS 判断对称二叉树

判断root.left和root.right是否互为镜像
递归判断 p和q 是否为镜像，is_mirror(p,q) 函数，
- p和q 均为空：对称。
- p和q 一个为空 一个不为空 或值不相对：不对称。
- 递归判断 ：p.left <-> q.right，p.right <-> q.left
  - 都互为镜像：对称
  - 否则：不对称

BFS 判断对称二叉树

构建队列，放入需要比较2个节点，初始放入 [左孩子,右孩子]，
队列有值做循环
- 队列出队 popleft，获得p和q
- p q 都为空：continue
- p q 一个为空或值不相同：不对称
- 放入需比较的2组孩子：p.left, q.right 和 p.right, q.left

6-102-二叉树的层序遍历

leetcode-102

层序遍历，逐层访问节点
每一层都是一个list元素

BFS 队列层次遍历

root 入队，while 队列不为空，做循环
- 根据队列长度获取当前层长度
- 循环出队n次，每出队一个节点，把其孩子入队

7-108-将有序数组转换为二叉搜索树

leetcode-108

给一个升序数组，变成一个平衡二叉搜索树

平衡二叉搜索树

搜索树：左 < 根 < 右，中序遍历是升序序列
平衡树：左右高度差 不超过1

中间元素作根节点递归建树

递归建树函数：build(left, right)
- 递归终止条件：区间无效，left > right
- 构建当前节点：选择中间数字 ，mid = (left + right) // 2
- 递归构建 左子树和 右子树

8-098-验证二叉搜索树

leetcode-098

验证一棵树，是否为BST (二叉搜索树)，左 < 中 < 右

特别注意

常见错误：只检查当前节点左孩子 < 根，右孩子 > 根
需满足严格小于：左子树所有节点 < 根 < 右子树所有节点
递归进入子树：需带上上下界 数值范围，BST是严格小于，不能等于

DFS validate 验证二叉搜索树

构建 dfs_validate(node, 最小值, 最大值) 函数
递归终止条件：节点为空，返回 True
判断当前节点：需满足 min_val < val < max_val
递归判断左孩子：(node.left, min_val, node.val)
- 判断左孩子：最大值为node.val
递归判断右孩子：(node.right, node.val, max_val)
- 判断右孩子：最小值为node.val

栈中序遍历判断二叉搜索

栈+中序遍历，记录上一个数。
需满足：当前数 > 上一个数；否则 不为BST

9-230-二叉搜索树中第K小的元素

leetcode-230

给一个BST，寻找第k小的元素

核心思路

栈 + 中序遍历，记录第k个元素即可

栈中序遍历找第k小方法

BST，中序遍历，设置索引，第k个遍历 则是第k小元素
构建栈stack和curr=root
当curr不为空或栈不为空，执行循环
- curr往左走，左孩子入栈，到达最左
- 栈顶出栈 访问最左元素，记录cur_idx+=1，若cur_idx等于k则为目标元素。
- curr 转向右子树

10-199-二叉树的右视图

leetcode-199

从右侧看二叉树，按层依次输出能看到的所有节点

层次遍历输出每层最后元素

层次遍历，输出每一层的最后一个元素
标准使用队列做层次遍历，记录每层的最后一个元素。

11-114-二叉树展开为链表

leetcode-114

输入：二叉树root；输出：root
二叉树展开为链表，仍用TreeNode类，左节点为空，右节点指向链表下一个节点。
链表顺序 与原二叉树 先序遍历相同：根->左->右

栈先序遍历再链接链表

栈先序遍历，依次存储节点，再依次链接成链表
构建栈，root先入栈，构建node_list 存储节点
当栈不为空，执行循环
- 栈顶元素 出栈，访问根节点
- 右孩子 先入栈，后访问右孩子
- 左孩子 后入栈，先访问左孩子
依照顺序，设置右孩子，串联成链表。
- 注意末尾节点 左右孩子均为空。

左右节点原地链接法

依次遍历，处理curr节点
- 如果没有左子树，则不用处理。
- 如果有左子树，
  - 找到左子树的最右/末尾节点，即先序遍历 的末尾节点
  - 把右子树接到左子树 最右节点的右孩子
  - 把整个左子树移到右边变右子树，清空左孩子 left=None
- 处理右子树，curr = curr.right

12-105-从前序与中序遍历序列构造二叉树

leetcode-105

给定前序和中序遍历结果，来反向构造二叉树
无重复元素

特点

先序：[根, {左子树}, {右子树}]
中序：[{左子树}, 根, {右子树}]

递归思路

在先序里，第一个位置为根节点。
在中序里，找到根节点位置；左边则为左子树，右边为右子树。
递归构建 左右子树

核心步骤

记录节点 在中序中的位置 val2inpos
构建helper递归函数，传入先序 起始位置、中序 起始位置，进行递归构建
- 递归终止条件：start > end
- 确定根节点和根中序位置：先序 起始位置 + val2inpos
- 确定左右子树长度：根据根中序位置
- 确定左孩子边界范围，递归构建左孩子。
  - 小心起始下标：根据是否包含，+1，+0，-1。
- 确定右孩子边界范围，递归构建右孩子。小心起始下标。
- 设置root的左右孩子，返回root
递归开始：helper(0, n-1, 0, n-1)

13-437-路径总和3

leetcode-437

给一颗树和target_sum，求问多少种路径，使得节点求和为target_sum。
路径只能向下走，不限制起始位置，可以从任何位置开始，到任何位置结束。

暴力法：每个节点作为起点算一遍

前缀和计数三个核心变量

前缀和：根节点到当前节点 求和
前缀和余数： 当前前缀和 - 目标和
前缀和计数count dict：具体前缀和数值 出现次数

DFS+前缀和核心步骤

定义count变量，dfs(node, current_sum)递归函数，执行dfs(root, 0)
递归求解 路径次数
- 终止条件：node为空，返回0
- 计算当前节点前缀和、前缀和余数，
- 基于count 计算当前node 作为叶子节点的路径数量
- 更新count，递归计算 左右子树路径数量，还原count
- 返回路径数量：当前节点数量 + 左子树数量 + 右子树数量

14-236-二叉树的最近公共祖先

leetcode-236

输入：root节点，节点p，节点q
输出：节点p和q的最近公共祖先

root是p和q的最近公共祖先3种条件

p和q分别在root的子树中，分别位于2侧。
p==root，q在root的左或右侧。
q==root，p在root的左或右侧。

DFS后序查找最近公共祖先

递归终止条件：越过叶子节点root为空、root=p、root=q
递归在左右子树中查找：返回值标记为left和right
情况判断：
- 如果left和right 都不为空：p和q分别在root左右两侧，返回root
- 如果left不为空：都在left里，返回left
- 如果right不为空：都在right里，返回right
- 都为空：返回空

15-124-二叉树中的最大路径和

leetcode-124

输入：二叉树
输出：最大路径和

DFS后序计算最大路径和核心流程

定义：全局变量max_sum，记录最大值
定义：dfs函数，计算以node为顶点的单线最大收益。但在中间去计算v型收益，更新最值
开始递归dfs(root)，返回最值

DFS函数

递归终止条件：node为空，返回0收益
递归计算 左孩子收益、右孩子收益，务必 和0做max取最值，为负的孩子 就不要了。
计算v型收益 left+node+right，更新最大权重，但不能上报，不满足dfs深度单线条件
返回当前节点的最大单线收益，要么+左或+右或仅自己

题目

1-094-二叉树的中序遍历

leetcode-094

输入：二叉树根节点
输出：中序遍历结果，左-> 根 -> 右

DFS中序遍历

DFS 中序遍历

递归终止：空节点则返回[]
递归遍历 左孩子
访问 根节点
递归遍历 右孩子

python

def inorderTraversal_dfs(self, root: Optional[TreeNode]) -> List[int]:
    if not root:
        return []

    res = []
    # 递归遍历左孩子
    left_res = self.inorderTraversal_dfs(root.left)
    res.extend(left_res)
    # 访问根节点
    res.append(root.val) 
    # 递归遍历右孩子
    right_res = self.inorderTraversal_dfs(root.right)
    res.extend(right_res)
    return res

栈中序遍历

左-> 根 -> 右
构建栈stack和curr=root
当curr不为空或栈不为空，执行循环
- curr往左走，左孩子入栈，到达最左
- 栈顶出栈 访问最左元素
- curr 转向右子树

python

def inorderTraversal_stack(self, root: Optional[TreeNode]) -> List[int]:
    """栈先入后出
    """
    res = []
    stack = []
    curr = root
    while curr or stack:  
        # 1. 尽量往左走，路径全部入栈
        while curr:
            stack.append(curr)
            curr = curr.left

        # 2. 出栈，已达最左或当前子树的根部
        curr = stack.pop()
        res.append(curr.val)

        # 3. 转向右子树
        curr = curr.right
    return res

1-114-二叉树的前序遍历

leetcode-114

根 -> 左 -> 右

栈前序遍历

构建栈，root先入栈
当栈不为空，执行循环
- 栈顶元素 出栈，访问根节点
- 右孩子 先入栈，后访问右孩子
- 左孩子 后入栈，先访问左孩子

python

def preorderTraversal_stack(self, root: Optional[TreeNode]) -> List[int]:
    res = []
    if not root:
        return res 

    stack = [root]

    while stack:
        # 1. 栈顶元素出栈
        curr = stack.pop()
        res.append(curr.val)

        # 2. 右孩子先入栈，后出
        if curr.right:
            stack.append(curr.right)

        # 3. 左孩子后入栈，先出
        if curr.left:
            stack.append(curr.left)
    return res

1-145-二叉树的后序遍历

信息

leetcode-145

后序遍历：左 -> 右 -> 根

栈后序遍历

栈后续遍历

后序 vs 先序

先序：根 -> 左 -> 右
后序：左 -> 右 -> 根 。
可先按照先序得 根 右左，翻转回 左右 根

栈先序翻转得后序法

先得 根 -> 右 -> 左，再反转回 左 -> 右 -> 根
构建栈，root先入栈
当栈不为空，执行循环
- 栈顶元素 出栈，访问 根节点
- 左孩子 先入栈，右孩子 再入栈
  - 先访问右孩子、再访问左孩子
得遍历结果 根 右左
把遍历结果 倒序则遍后序， 左右 根

python

def postorderTraversal_stack(self, root: Optional[TreeNode]) -> List[int]:
    res = []
    if not root:
        return res 

    stack = [root]

    while stack:
        # 1. 栈顶元素出栈，访问
        curr = stack.pop()
        res.append(curr.val)

        # 2. 左孩子入栈，后访问
        if curr.left:
            stack.append(curr.left)

        # 3. 右孩子入栈，先访问
        if curr.right:
            stack.append(curr.right)

    return res[::-1]

6-102-二叉树的层序遍历

leetcode-102

层序遍历，逐层访问节点
每一层都是一个list元素

BFS 层次遍历

BFS 队列层次遍历

构建队列，root 入队
队列不为空，执行循环
- 根据队列长度获取当前层长度
- 循环出队n次，每出队一个节点，把其左右孩子 依次入队

python

def levelOrder_deque(self, root: Optional[TreeNode]) -> List[List[int]]:
    res = []
    if not root:
        return []
    queue = deque([root])
    while queue:
        # 当前层的数量
        level_size = len(queue)  
        level_vals = []
        for _ in range(level_size):  
            node = queue.popleft()
            level_vals.append(node.val)
            # 下一层的入队列
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        res.append(level_vals)
    return res

2-104-二叉树的最大深度

leetcode-104

求根节点到叶子节点的最大长度

DFS 计算深度

深度DFS 递归解法

递归终止：节点为空，返回0
递归计算： 左孩子深度、右孩子深度
1 + max(left_depth, right_depth)

python

def maxDepth_dfs(self, root: Optional[TreeNode]) -> int:
    if not root:
        return 0
    left_depth = self.maxDepth_dfs(root.left)
    right_depth = self.maxDepth_dfs(root.right)
    return 1 + max(left_depth, right_depth)

BFS 计算深度

队列层次遍历

构建队列deque，
循环每次处理1层，计算当前层size=len(queue)
访问当前节点时，叶子节点按左右依次入队。

BFS 计算深度

root 入队，while 队列不为空，做循环
- 根据队列长度获取当前层长度
- 循环出队n次，每出队一个节点，把左右孩子依次入队
- 每层：深度 += 1

python

def maxDepth_bfs(self, root: Optional[TreeNode]) -> int:
    if not root:
        return 0
    queue = deque([root])
    depth = 0

    while queue:
        # 当前层的节点数量
        level_size = len(queue)
        for _ in range(level_size):
            # 先进先出
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        depth += 1
    return depth

3-226-翻转二叉树

leetcode-226

翻转二叉树，左右节点 做交换。

DFS 翻转

DFS 翻转二叉树

递归终止
递归翻转左孩子、递归翻转右孩子
翻转当前root的左右孩子

python

def invertTree_dfs(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
    # 1. 递归终止条件
    if not root:
        return root
		# 2. 递归翻转左右孩子
    left = self.invertTree_dfs(root.left)
    right = self.invertTree_dfs(root.right)
    # 3. 翻转当前节点的左右孩子
    root.right = left 
    root.left = right
    return root

BFS 翻转

BFS 翻转二叉树

构建队列，root入队
队列有值做循环
- 当前node = 队首出队
- 交换 当前node的左右孩子
- 当前node的左右孩子 依次入队。仅不为空时才入队。

python

def invertTree_bfs(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
    if not root:
        return root
    queue = deque([root])

    while queue:
        node = queue.popleft() 
        node.right, node.left = node.left, node.right  
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return root

4-101-对称二叉树

leetcode-101

判断一棵树是否是对称二叉树，它的左子树和右子树是否互为镜像
- 左树的 左孩子 == 右树的 右孩子
- 左树的 右孩子 == 右树的 左孩子

DFS 判断对称二叉树

判断root.left和root.right是否互为镜像
递归判断 p和q 是否为镜像，is_mirror(p,q) 函数，
- p和q 均为空：对称。
- p和q 一个为空 一个不为空 或值不相对：不对称。
- 递归判断 ：p.left <-> q.right，p.right <-> q.left
  - 都互为镜像：对称
  - 否则：不对称

python

def isSymmetric_dfs(self, root: Optional[TreeNode]) -> bool:
    if not root:
        return True

    def is_mirror(p, q):  
        # 两个都为空，是对称的
        if not p and not q:
            return True
        # 一个为空一个不为，或者值不相等，不对称
        if not p or not q or p.val != q.val:
            return False

        # 关键：比较 p 的左和 q 的右，以及 p 的右和 q 的左
        return isMirror(p.left, q.right) and isMirror(p.right, q.left)  

    return is_mirror(root.left, root.right)

BFS 判断对称二叉树

构建队列，放入需要比较2个节点，初始放入 [左孩子,右孩子]，
队列有值做循环
- 队列出队 popleft，获得p和q
- p q 都为空：continue
- p q 一个为空或值不相同：不对称
- 放入需比较的2组孩子：p.left, q.right 和 p.right, q.left

python

def isSymmetric_bfs(self, root: Optional[TreeNode]) -> bool:
    if not root:
        return True

    # 初始放入需要比较的2个节点，初始放入左孩子和右孩子，
    queue = deque([(root.left, root.right)]) 

    while queue:
      	# 获得当前需要比较的2个节点，p和q
        p, q = queue.popleft()
        # p q 都为空
        if not p and not q:
            continue
        # p q 一个为空或值不相同
        if not p or not q or p.val != q.val:
            return False
        # 放入需要比较的孩子
        queue.append((p.left, q.right))
        queue.append((p.right, q.left))
    return True

5-543-二叉树的直径

leetcode-543

直径：二叉树任意两个节点之间的距离，边的数量。

最大直径3种可能性

经过根节点、仅在左子树、仅在右子树
最大直径 = max(root_diameter, left_diameter, right_diameter)
- root作为最高点，左孩子作为最高点，右孩子作为最高点
当前节点作为最高点：直径 = left_depth + right_depth
- 深度：见上文，BFS 或 DFS 计算都可

DFS 计算直径

记录全局最大直径变量，只DFS 一次
DFS 遍历计算每个节点作为最高点的直径，如超过最大值，则更新。

一次dfs，记录全局变量，写法

python

def diameterOfBinaryTree_simple_dfs(self, root: Optional[TreeNode]) -> int:
    if not root:
        return 0
    # 1. 记录全局最大直径变量
    self.max_diameter = 0

    def max_depth_dfs(node):
      	# 1. DFS 终止条件
        if not node:
            return 0
        # 2. 递归计算做优化孩子深度
        left_depth = max_depth_dfs(node.left)
        right_depth = max_depth_dfs(node.right)
        # 3. 计算当前节点作为最高节点的直径
        current_node_diamter = left_depth + right_depth  
        if current_node_diamter > self.max_diameter:  
            self.max_diameter = current_node_diamter
        # 4. 正常返回深度
        return 1 + max(left_depth, right_depth)
    max_depth_dfs(root)  
    return self.max_diameter

超时写法：遍历了多次dfs

python

def max_depth_dfs(self, root: Optional[TreeNode]) -> int:
    if not root:
        return 0
    left_depth = self.max_depth_dfs(root.left)
    right_depth = self.max_depth_dfs(root.right)
    depth = 1 + max(left_depth, right_depth)
    return depth

def diameterOfBinaryTree_timeout_dfs(self, root: Optional[TreeNode]) -> int:
    """ 进行了多次的dfs，会超时
    """
    if not root:
        return 0

    # 1. 当前root作为最高点，最大直径
    left_depth = self.max_depth_dfs(root.left)
    right_depth = self.max_depth_dfs(root.right)
    root_diameter = left_depth + right_depth

    # 2. 左孩子作为最高点，最大直径
    left_diameter = self.diameterOfBinaryTree_timeout_dfs(root.left)

    # 3. 右孩子作为最高点，最大直径
    right_diameter = self.diameterOfBinaryTree_timeout_dfs(root.right)

    return max(root_diameter, right_diameter, left_diameter)

7-108-将有序数组转换为二叉搜索树

leetcode-108

给一个升序数组，变成一个平衡二叉搜索树

平衡二叉搜索树

搜索树：左 < 根 < 右，中序遍历是升序序列
平衡树：左右高度差 不超过1

中间元素作根节点递归建树

递归建树函数：build(left, right)
- 递归终止条件：区间无效，left > right
- 选择中间数字 构建当前节点。mid = (left + right) // 2
- 递归构建 左子树、递归构建 右子树

python

def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
    if not nums:
        return None

    def build(left, right):
        # 递归终止条件：区间无效
        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)

8-098-验证二叉搜索树

leetcode-098

验证一棵树，是否为BST (二叉搜索树)，左 < 中 < 右

特别注意

常见错误：只检查当前节点左孩子 < 根，右孩子 > 根
需满足严格小于：左子树所有节点 < 根 < 右子树所有节点
递归进入子树：需带上上下界 数值范围，BST是严格小于，不能等于。

DFS 错误写法

错误观点：左子树valid 、右子树valid --> 整棵树都是BST
还需保证：左子树所有节点 < 根节点 < 右子树所有节点

python

def isValidBST_dfs(self, root: Optional[TreeNode]) -> bool:
    if not root:
        return True

    if root.left:
        if root.left.val >= root.val:
            return False
        left_valid = self.isValidBST_dfs(root.left)
        if not left_valid:
            return False

    if root.right:
        if root.right.val <= root.val:
            return False
        right_valid = self.isValidBST_dfs(root.right)
        if not right_valid:
            return False
    return True

DFS validate 验证二叉搜索树

重要

构建 dfs_validate(node, 最小值, 最大值) 函数
递归终止条件：节点为空，返回 True
判断当前节点：需满足 min_val < val < max_val
递归判断左孩子：(node.left, min_val, node.val)
- 判断左孩子：最大值为node.val
递归判断右孩子：(node.right, node.val, max_val)
- 判断右孩子：最小值为node.val

python

def isValidBST_dfs(self, root: Optional[TreeNode]) -> bool:
    """递归解法
    """
    def validate(node, min_val, max_val):
        if not node:
            return True
        # 注意BST是严格小于的逻辑，不能等于
        if node.val <= min_val or node.val >= max_val:  
            return False
        left_valid = validate(node.left, min_val, node.val) 
        if left_valid:
            right_valid = validate(node.right, node.val, max_val) 
            if right_valid:
                return True
        return False

    return validate(root, float('-inf'), float('inf'))

DFS中序遍历判断二叉搜索

中序遍历严格递增判断法

先中序遍历树，再判断是否严格单调递增
缺点：耗时久

中序遍历DFS和Stack方法代码

python

def inorder_dfs(self, root: Optional[TreeNode]) -> bool:
    res = []
    if not root:
        return []
    left_order = self.inorder_dfs(root.left)
    right_order = self.inorder_dfs(root.right)
    res.extend(left_order)
    res.append(root.val)
    res.extend(right_order)
    return res

def inorder_stack(self, root: Optional[TreeNode]) -> bool:
    res = []
    if not root:
        return []

    stack = []
    curr = root
    while stack or curr:
        # 到达最左
        while curr:
            stack.append(curr)
            curr = curr.left 
        # 出栈
        curr = stack.pop()
        res.append(curr.val)

        # 转向右子树
        curr = curr.right

    return res

严格递增判断是否二叉搜索树

python

def isValidBST_inorder(self, root: Optional[TreeNode]) -> bool:
    # vals = self.inorder_dfs(root)
    vals = self.inorder_stack(root)  
    if not vals:
        return True
    if len(vals) == 1:
        return True

    prev = vals[0]
    for i in range(1, len(vals)):
        val = vals[i]
        if prev >= val:  
            return False
        prev = val
    return True

栈中序遍历判断二叉搜索

栈+中序遍历，记录上一个数。
需满足：当前数 > 上一个数；否则 不为BST

python

def isValidBST_stack(self, root: Optional[TreeNode]) -> bool:
    """
    BST：中序必须满足：左 < 根 < 右
    栈遍历，当前数必须大于上一个数
    """
    if not root:
        return True

    stack = []
    curr = root
    pre_val = float('-inf')

    while curr or stack:
        # 左侧，入栈
        while curr:
            stack.append(curr)
            curr = curr.left
        # 判断当前值是否大于前一个值
        curr = stack.pop()
        if not curr.val > pre_val:  
            return False
        # 更新上一个数
        pre_val = curr.val

        # 转向右子树
        curr = curr.right 
    return True

9-230-二叉搜索树中第K小的元素

leetcode-230

给一个BST，寻找第k小的元素

核心思路

栈 + 中序遍历，记录第k个元素即可

栈中序遍历找第k小方法

BST，中序遍历，设置索引，第k个遍历 则是第k小元素
构建栈stack和curr=root
当curr不为空或栈不为空，执行循环
- curr往左走，左孩子入栈，到达最左
- 栈顶出栈 访问最左元素，记录cur_idx+=1，若cur_idx等于k则为目标元素。
- curr 转向右子树

python

def kthSmallest_stack(self, root: Optional[TreeNode], k: int) -> int:
    """
    栈，中序遍历，第k个数值即是
    """
    if not root:
        return -1

    stack = []
    curr = root
    cur_idx = 0

    while curr or stack:
        # 向左走
        while curr:
            stack.append(curr)
            curr = curr.left

        # 出栈
        curr = stack.pop()
        cur_idx += 1
        if cur_idx == k:  
            return curr.val

        # 转向右节点
        curr = curr.right
    return -1

频繁修改记录size优化

问题

如果树经常插入/删除，且频繁查询第k小，怎么办？
当前算法复杂度为 $O (H + k)$ ， $H$ 为树高， $k$ 为第k小，如果k很大，则性能会下降。

解决方法

每个节点维护size属性：当前节点为根，总节点个数。
逻辑
- 获取左子树 left_size
- 如果k==left_size+1：当前节点就是第k小
- 如果k < left_size：去左子树找第k小
- 如果k>left_size+1：去右子树找第k-left_size-1小

10-199-二叉树的右视图

leetcode-199

从右侧看二叉树，按层依次输出能看到的所有节点

解法

层次遍历，输出每一层的最后一个元素即可。

层次遍历输出每层最后元素

标准使用队列做层次遍历，记录每层的最后一个元素。

python

def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
    """层次遍历，输出每一层最后一个元素
    """
    res = []
    if not root:
        return res

    # 层次遍历，先进先出
    queue = deque([root])

    while queue:
        # 每一层出队level_size次
        level_size = len(queue) 
        for i in range(level_size):
            node = queue.popleft()
            # 下一层的左右孩子入队
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
            if i == level_size - 1: 
                res.append(node.val)
    return res

11-114-二叉树展开为链表

leetcode-114

输入：二叉树root；输出：root
二叉树展开为链表，仍用TreeNode类，左节点为空，右节点指向链表下一个节点。
链表顺序 与原二叉树 先序遍历相同：根->左->右

栈先序遍历再链接链表

核心思想

栈先序遍历，依次存储节点，再依次链接成链表

栈先序遍历

构建栈，root先入栈，构建node_list 存储节点
当栈不为空，执行循环
- 栈顶元素 出栈，访问根节点
- 右孩子 先入栈，后访问右孩子
- 左孩子 后入栈，先访问左孩子
依照顺序，设置右孩子，串联成链表。
- 注意末尾节点 左右孩子均为空。

python

def flatten_preoder_stack(self, root: Optional[TreeNode]) -> None:
    if not root:
        return None

    # 1. 先序遍历，依照顺序存储节点列表
    nodes_list = []
    stack = [root] 

    while stack:  
        # 出栈
        node = stack.pop()  
        nodes_list.append(node)
        # 右孩子入栈，先入后出
        if node.right:
            stack.append(node.right)
        # 左孩子入栈，后入先出
        if node.left:
            stack.append(node.left)

    # 2. 依照顺序，设置右孩子，串联成链表
    for i in range(0, len(nodes_list)-1):
        node = nodes_list[i]
        node.left = None
        node.right = nodes_list[i+1] 

    # 3. 最后一个节点 左孩子右孩子设为空
    nodes_list[-1].left = None 
    nodes_list[-1].right = None 

    return root

Morris左右节点原地移植算法

左右节点原地链接法

核心步骤

依次遍历，处理curr节点
- 如果没有左子树，则不用处理。
- 如果有左子树，
  - 找到左子树的最右/末尾节点，即先序遍历 的末尾节点
  - 把右子树接到左子树 最右节点的右孩子
  - 把整个左子树移到右边变右子树，清空左孩子 left=None
- 处理右子树，curr = curr.right

原理

左子树的最右节点，是左边末尾节点。
右子树的节点，是根节点的下一个节点，适合放在左子树最后节点的右边。
画图示意比较好

python

def flatten_selfmove_morris(self, root: Optional[TreeNode]) -> None:
    """
    原地移动，把节点的右子树挂到左子树的最右节点，再把整个左子树挂到右边去
    """
    curr = root
    while curr:
        if curr.left:
            # 1. 找到左子树的最右节点
            predecssor = curr.left
            while predecssor.right: 
                predecssor = predecssor.right

            # 2. 把原来的右子树接到左子树最右节点
            predecssor.right = curr.right 

            # 3. 把左子树，移到右边，左子树设为空
            curr.right = curr.left 
            curr.left = None 
        # 4. 继续处理右孩子，下一个节点
        curr = curr.right
    return root

12-105-从前序与中序遍历序列构造二叉树

leetcode-105

给定前序和中序遍历结果，来反向构造二叉树
无重复元素

特点

先序：[根, {左子树}, {右子树}]
中序：[{左子树}, 根, {右子树}]

寻找根节点左右递归构建

根节点左右子树递归构建

递归思路

在先序里，第一个位置为根节点。
在中序里，找到根节点位置；左边则为左子树，右边为右子树。
递归构建 左右子树

核心步骤

记录节点 在中序中的位置 val2inpos
构建helper递归函数，传入先序 起始位置、中序 起始位置，进行递归构建
- 递归终止条件：start > end
- 确定根节点和根中序位置：先序 起始位置 + val2inpos
- 确定左右子树长度：根据根中序位置
- 确定左孩子边界范围，递归构建左孩子。
  - 小心起始下标：根据是否包含，+1，+0，-1。
- 确定右孩子边界范围，递归构建右孩子。小心起始下标。
- 设置root的左右孩子，返回root
递归开始：helper(0, n-1, 0, n-1)

python

def buildTree_recursion(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
    """ 此二叉树，输入无重复元素
    """
    if not preorder or not inorder:
        return None

    # 根据节点值快速找到在中序遍历中的位置
    val2inpos = {val: index for index, val in enumerate(inorder)}  

    def helper(pre_start, pre_end, in_start, in_end):
        """
        递归构建方法，全局访问preorder, inorder
        Args:
            pre_start: 前序开始
            pre_end:
            in_start: 后续开始
            in_in_endright:
        """
        # 递归终止条件
        if pre_start > pre_end or in_start > in_end:
            return None

        # 1. 确定根节点，pre的第一个位置
        root_val = preorder[pre_start]
        root = TreeNode(root_val)

        # 2. 确定根节点在中序中的位置
        root_in_pos = val2inpos[root_val]

        # 3. 根据中序确定左右子树长度
        left_tree_size = root_in_pos - in_start  
        right_tree_size = in_end - root_in_pos

        # 4. 确定左孩子边界范围，递归构建左孩子
        left_node = helper(  
            pre_start+1,
            pre_start+left_tree_size,
            in_start,
            in_start+left_tree_size-1
        )

        # 5. 确定右孩子边界范围，递归构建右孩子
        right_node = helper(  
            pre_start+left_tree_size+1,
            pre_end,
            root_in_pos+1,
            in_end
        )

        # 6. 设置root的左右孩子
        root.left = left_node
        root.right = right_node
        return root

    n = len(preorder)
    return helper(0, n-1, 0, n-1)

13-437-路径总和3

leetcode-437

给一颗树和target_sum，求问多少种路径，使得节点求和为target_sum。
路径只能向下走，不限制起始位置，可以从任何位置开始，到任何位置结束。

暴力法：每个节点作为起点算一遍

DFS前缀和余数求次数

前缀和计数三个核心变量

前缀和：根节点到当前节点 求和
前缀和余数： 当前前缀和 - 目标和
前缀和计数count dict：具体前缀和数值 出现次数

DFS+前缀和核心步骤

定义count变量，dfs(node, current_sum)递归函数，执行dfs(root, 0)
递归求解 路径次数
- 终止条件：node为空，返回0
- 计算当前节点前缀和、前缀和余数，
- 基于count 计算当前node 作为叶子节点的路径数量
- 更新count，递归计算 左右子树路径数量，还原count
- 返回路径数量：当前节点数量 + 左子树数量 + 右子树数量

python

def pathSum_dfs_prefixsum(self, root: Optional[TreeNode], targetSum: int) -> int:
    """ dfs + 前缀和，求解pathSum
    """

    if not root:
        return 0
		
    # 前缀和计数
    count = defaultdict(int) 
    count[0] = 1

    def dfs(node, current_sum):
        """ dfs，计算和当前node相关的路径和
        """
        if not node:
            return 0

        # 计算以当前节点为终止节点的前缀和
        current_sum += node.val

        # 递归计算左子树路径数量、右子树路径数量
        count[current_sum] += 1
        left_cnt = dfs(node.left, current_sum)
        right_cnt = dfs(node.right, current_sum)
        count[current_sum] -= 1

        # 计算以当前节点为叶子节点的路径数量
        extra_sum = current_sum - targetSum
        curr_node_cnt = count[extra_sum]

        # 整体路径数量：当前节点为结尾的路径数量+左子树的路径数量+右子树的路径数量
        return curr_node_cnt + left_cnt + right_cnt


    return dfs(root, 0)

14-236-二叉树的最近公共祖先

leetcode-236

输入：root节点，节点p，节点q
输出：节点p和q的最近公共祖先

DFS后序遍历查找节点

root是p和q的最近公共祖先3种条件

p和q分别在root的子树中，分别位于2侧。
p==root，q在root的左或右侧。
q==root，p在root的左或右侧。

DFS查找最近公共祖先

递归终止条件：越过叶子节点root为空、root=p、root=q
递归在左右子树中查找：返回值标记为left和right
情况判断：
- 如果left和right 都不为空：p和q分别在root左右两侧，返回root
- 如果left不为空：都在left里，返回left
- 如果right不为空：都在right里，返回right
- 都为空：返回空

python

def lowestCommonAncestor_dfs(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    """ dfs查找最近公共祖先
    """

    # 1. 递归终止条件：root为空到达叶子节点、root=p，root=q
    if not root or root == p or root == q:
        return root

    # 2. DFS遍历：去左子树和右子树中查找
    left = self.lowestCommonAncestor_dfs(root.left, p, q)
    right = self.lowestCommonAncestor_dfs(root.right, p, q)

    # 3. 处理查找结果
    if left and right:
        # p和q分别在root的左右2侧，root为最近公共祖先
        return root

    # p和q仅在单独一侧 或 都不在
    return left if not right else right

15-124-二叉树中的最大路径和

leetcode-124

输入：二叉树
输出：最大路径和

DFS后序计算最大路径和

核心流程

定义：全局变量max_sum，记录最大值
定义：dfs函数，计算以node为顶点的单线最大收益。但在中间去计算v型收益，更新最值
开始递归dfs(root)，返回最值

DFS函数

递归终止条件：node为空，返回0收益
递归计算 左孩子收益、右孩子收益，务必 和0做max取最值，为负的孩子 就不要了。
计算v型收益 left+node+right，更新最大权重，但不能上报，不满足dfs深度单线条件
返回当前节点的最大单线收益，要么+左或+右或仅自己

python

def maxPathSum_dfs(self, root: Optional[TreeNode]) -> int:
    # 定义全局变量，记录最大值
    self.max_sum = float('-inf')

    # 递归函数，计算以node为顶点的 单线最大收益，但中间去计算v型收益，更新最值
    def dfs(node):
        # 1. 递归终止条件
        if not node:
            return 0

        # 2. 递归计算左孩子收益、右孩子收益，一定做max，为负就不要了
        left_gain = max(dfs(node.left), 0)  
        right_gain = max(dfs(node.right), 0)  

        # 3. 计算v型收益，更新最大权重，但不能上报，不满足dfs条件。
        cur_arch_sum = left_gain + node.val + right_gain
        self.max_sum = max(self.max_sum, cur_arch_sum)

        # 4. 返回当前节点的最大单线收益，要么+左或+右或仅自己
        return node.val + max(left_gain, right_gain)  

    # 开始递归
    dfs(root)
    return self.max_sum

基础知识 ​

二叉树的遍历 ​

队列和栈 ​

题目总结 ​

题目 ​

1-094-二叉树的中序遍历 ​

DFS中序遍历 ​

栈中序遍历 ​

1-114-二叉树的前序遍历 ​

栈前序遍历 ​

1-145-二叉树的后序遍历 ​

栈后序遍历 ​

6-102-二叉树的层序遍历 ​

BFS 层次遍历 ​

2-104-二叉树的最大深度 ​

DFS 计算深度 ​

BFS 计算深度 ​

3-226-翻转二叉树 ​

DFS 翻转 ​

BFS 翻转 ​

4-101-对称二叉树 ​

DFS 判断对称二叉树 ​

BFS 判断对称二叉树 ​

5-543-二叉树的直径 ​

DFS 计算直径 ​

7-108-将有序数组转换为二叉搜索树 ​

中间元素作根节点递归建树 ​

8-098-验证二叉搜索树 ​

DFS 错误写法 ​

DFS validate 验证二叉搜索树 ​

DFS中序遍历判断二叉搜索 ​

栈中序遍历判断二叉搜索 ​

9-230-二叉搜索树中第K小的元素 ​

栈中序遍历找第k小方法 ​

频繁修改记录size优化 ​

10-199-二叉树的右视图 ​

层次遍历输出每层最后元素 ​

11-114-二叉树展开为链表 ​

栈先序遍历再链接链表 ​

Morris左右节点原地移植算法 ​

12-105-从前序与中序遍历序列构造二叉树 ​

寻找根节点左右递归构建 ​

13-437-路径总和3 ​

暴力法：每个节点作为起点算一遍 ​

DFS前缀和余数求次数 ​

14-236-二叉树的最近公共祖先 ​

DFS后序遍历查找节点 ​

15-124-二叉树中的最大路径和 ​

DFS后序计算最大路径和 ​

基础知识

二叉树的遍历

队列和栈

题目总结

题目

1-094-二叉树的中序遍历

DFS中序遍历

栈中序遍历

1-114-二叉树的前序遍历

栈前序遍历

1-145-二叉树的后序遍历

栈后序遍历

6-102-二叉树的层序遍历

BFS 层次遍历

2-104-二叉树的最大深度

DFS 计算深度

BFS 计算深度

3-226-翻转二叉树

DFS 翻转

BFS 翻转

4-101-对称二叉树

DFS 判断对称二叉树

BFS 判断对称二叉树

5-543-二叉树的直径

DFS 计算直径

7-108-将有序数组转换为二叉搜索树

中间元素作根节点递归建树

8-098-验证二叉搜索树

DFS 错误写法

DFS validate 验证二叉搜索树

DFS中序遍历判断二叉搜索

栈中序遍历判断二叉搜索

9-230-二叉搜索树中第K小的元素

栈中序遍历找第k小方法

频繁修改记录size优化

10-199-二叉树的右视图

层次遍历输出每层最后元素

11-114-二叉树展开为链表

栈先序遍历再链接链表

Morris左右节点原地移植算法

12-105-从前序与中序遍历序列构造二叉树

寻找根节点左右递归构建

13-437-路径总和3

暴力法：每个节点作为起点算一遍

DFS前缀和余数求次数

14-236-二叉树的最近公共祖先

DFS后序遍历查找节点

15-124-二叉树中的最大路径和

DFS后序计算最大路径和