Blog of AgioPan
0%

数据结构与算法自学笔记（14）- 二叉树高频题目

Posted on In ,

引言

参照的是左程云的课程：https://space.bilibili.com/8888480/lists/3509640?type=series

本笔记是class036→037的内容，总结了二叉树相关的9+7=16道高频算法题目。class36涵盖了二叉树的遍历、序列化、构造、验证等核心操作，但不包含树型动态规划的内容。class037算是036的补充，讲了二叉树相关的另外7道高频算法题目，包含了最近公共祖先（LCA）问题、路径搜索、平衡性验证、搜索二叉树相关操作。

前置知识

在学习二叉树高频题目之前，需要掌握以下基础知识：

  • 队列用数组实现（讲解013）
  • 二叉树入门内容（讲解017~018）

重要说明

  • 本期和下期视频会讲解二叉树高频题目，但不含树型dp的题目
  • 树型dp问题会放在【必备】课程的动态规划大章节部分讲述
  • 树型dp中的换根dp问题会放在【扩展】课程的动态规划大章节部分讲述
  • AVL树的实现、树的左旋右旋等内容也会在【扩展】课程里讲述
  • 问题1又叫LCA问题，非常重要！Tarjan算法解决LCA的批量查询、树链剖分算法解决LCA的在线查询会在【扩展】课程讲述
  • 数组的打家劫舍问题变形很多，会在【必备】课程的动态规划大章节部分讲述
  • 再次强调树型dp的整体讲解，会在【必备】课程的动态规划大章节部分讲述

036【必备】二叉树高频题目-上-不含树型dp

初始化的二叉树类

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

题目一：二叉树的层序遍历

问题描述

给你二叉树的根节点 root，返回其节点值的层序遍历。（即逐层地，从左到右访问所有节点）

测试链接：https://leetcode.cn/problems/binary-tree-level-order-traversal/

核心思想

使用广度优先搜索（BFS）进行层序遍历，有两种实现方式：

  1. 普通BFS：使用队列存储节点，用哈希表记录每个节点的层级
  2. 优化BFS：按层处理，每次处理完整一层的所有节点

层序遍历的实现
层序遍历的实现2

算法实现

方法一：普通BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from collections import deque
from typing import List, Optional

# 提交时把方法名改为levelOrder，此方法为普通bfs（宽度/广度优先搜索，叫宽度搜索的原因是层的最大节点数为宽度），此题不推荐
def levelOrder1(self, root: Optional[TreeNode]) -> List[List[int]]:
    # 核心思想：标准的广度优先搜索（BFS）。
    # 使用一个队列存储待访问节点，同时用一个哈希表（字典）来记录每个节点所在的层级。
    ans = []
    if root:#根节点有东西
        # Python的deque是一个高效的双端队列，非常适合用于BFS
        queue = deque([root])
        # 字典用于存储 node -> level 的映射
        levels = {root: 0}
        while queue:# 队列不空的时候从队列中取出一个节点
            cur = queue.popleft()
            level = levels[cur]                
            # 如果当前层级是第一次遇到，就在ans中创建一个新列表
            if len(ans) == level: #ans 列表的长度总是等于当前已经处理过的层级数量，包括第0层，说明当前节点的层级 level 正好等于已经创建的层级数量，味着这个层级还没有被处理过，需要创建新的列表
                ans.append([])               
            # 将当前节点的值加入对应层级的列表
            ans[level].append(cur.val)              
            # 将子节点加入队列，并记录它们的层级
            if cur.left:
                queue.append(cur.left)
                levels[cur.left] = level + 1
            if cur.right:
                queue.append(cur.right)
                levels[cur.right] = level + 1
    return ans
    # 核心思想：标准的广度优先搜索（BFS），使用一个队列存储待访问节点，
    # 同时用一个哈希表（字典）来记录每个节点所在的层级。

方法二：优化BFS（推荐）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def levelOrder2(self, root: Optional[TreeNode]) -> List[List[int]]:
    # 核心思想：优化的广度优先搜索（BFS），按层处理。
    # 外层while循环控制层级，内层for循环精确地处理当前层的所有节点。
    # 这样就无需额外的哈希表来存储节点的层级信息。
    ans = []
    if root:
        queue = deque([root])
        while queue: # 当队列不为空，说明还有节点待处理
            size = len(queue) # 当前层的节点数量
            level_list = []
            for _ in range(size): # 精确处理当前层的所有节点
                cur = queue.popleft()
                level_list.append(cur.val)
                if cur.left: # 将下一层节点入队
                    queue.append(cur.left) 
                if cur.right:
                    queue.append(cur.right) # append是加在右边的
            ans.append(level_list)
    return ans

执行过程示例

以树结构 1->2,3; 2->4,5; 3->6 为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
初始状态：queue = [1], ans = []

处理第0层：
  size = 1, level_list = []
  取出节点1，level_list = [1]
  将节点2,3入队，queue = [2, 3]
  ans = [[1]]

处理第1层：
  size = 2, level_list = []
  取出节点2，level_list = [2]，将4,5入队
  取出节点3，level_list = [2, 3]，将6入队
  queue = [4, 5, 6]
  ans = [[1], [2, 3]]

处理第2层：
  size = 3, level_list = []
  依次取出4,5,6，level_list = [4, 5, 6]
  ans = [[1], [2, 3], [4, 5, 6]]

算法分析

  • 时间复杂度：O(N)，N为节点数
  • 空间复杂度：O(N)
  • 核心技巧：按层BFS遍历

题目二：二叉树的锯齿形层序遍历

问题描述

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）

测试链接：https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/

核心思想

在按层BFS的基础上，增加一个布尔标记 reverse。每一层遍历结束后，根据 reverse 的值决定是否要将当前层收集到的节点值列表进行反转。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# 提交以下的方法
# 用每次处理一层的优化bfs就非常容易实现
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
    # 核心思想：在按层BFS的基础上，增加一个布尔标记 `reverse`。
    # 每一层遍历结束后，根据 `reverse` 的值决定是否要将当前层收集到的节点值列表进行反转。
    # 然后切换 `reverse` 的状态，供下一层使用。
    ans = []
    if root:
        queue = deque([root])
        # false 代表从左往右
        # true 代表从右往左
        reverse = False
        while queue:
            size = len(queue)
            level_list = []
            
            # 步骤1: 像常规的按层BFS一样，先收集当前层的所有节点值
            for _ in range(size):
                cur = queue.popleft()
                level_list.append(cur.val)
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
            
            # 步骤2: 根据reverse标记决定是否反转当前层的列表
            if reverse:
                level_list.reverse()
            
            # 步骤3: 将处理好的层列表加入结果，并切换reverse标记
            ans.append(level_list)
            reverse = not reverse
    return ans

算法分析

  • 时间复杂度：O(N)
  • 空间复杂度：O(N)
  • 核心技巧：层序遍历 + 交替反转

题目三：二叉树的最大特殊宽度

问题描述

给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树的宽度与满二叉树相同，但不一定是满的。

测试链接：https://leetcode.cn/problems/maximum-width-of-binary-tree/

核心思想

给每个节点进行编号，就像在一个完全二叉树中一样。根节点编号为1，其左子节点为 2i，右子节点为 2i + 1。每一层的宽度就等于该层最右边节点的编号减去最左边节点的编号，再加1。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
    # 核心思想：给每个节点进行编号，就像在一个完全二叉树中一样。
    # 根节点编号为1，其左子节点为 2*i，右子节点为 2*i + 1。
    # 每一层的宽度就等于该层最右边节点的编号减去最左边节点的编号，再加1。
    # 我们使用按层BFS来遍历，同时在队列中存储 (节点, 编号) 对。
    if not root:
        return 0

    ans = 1
    # 队列中存储 (节点, 节点编号) 的元组
    queue = deque([(root, 1)])
    
    while queue:
        size = len(queue)
        # 记录当前层的起始编号
        start_id = queue[0][1]
        
        # 遍历当前层的所有节点
        for i in range(size):
            node, node_id = queue.popleft()
            
            # 在遍历到当前层最后一个节点时，计算宽度，这个是额外的步骤
            if i == size - 1:
                ans = max(ans, node_id - start_id + 1)

            # 将子节点及其新编号加入队列
            if node.left:
                queue.append((node.left, node_id * 2))
            if node.right:
                queue.append((node.right, node_id * 2 + 1))
    return ans

算法分析

  • 时间复杂度：O(N)
  • 空间复杂度：O(N)
  • 核心技巧：完全二叉树编号规则

题目四：求二叉树的最大深度、最小深度

问题描述

  1. 求二叉树的最大深度
  2. 求二叉树的最小深度

测试链接：

核心思想

最大深度

核心思想：递归。一棵树的最大深度等于其左、右子树最大深度中的较大者，再加1（根节点本身）。空树的深度为0，这是递归的基准情况，一定要到叶节点底部。

最小深度

递归，但需要特殊处理。最小深度是从根节点到最近的”叶子节点”的路径长度。如果一个节点只有一个子树，那么我们必须沿着这个非空的子树继续寻找叶子节点。

求子树最大or小深度

算法实现

最大深度

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

最小深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def minDepth(self, root: Optional[TreeNode]) -> int:
    if not root:
        # 当前的树是空树
        return 0
        
    left_depth = self.minDepth(root.left)
    right_depth = self.minDepth(root.right)

    # case 1: 如果左子树或右子树为空，我们不能取它为最小值（因为那条路没有叶子）。
    # 此时必须走另一条非空的路。`left_depth + right_depth + 1` 巧妙地处理了
    # (左=0, 右=N) -> N+1 和 (左=N, 右=0) -> N+1 的情况。
    if left_depth == 0 or right_depth == 0:
        return left_depth + right_depth + 1
    
    # case 2: 如果左右子树都不为空，那么最小深度就是两者中的较小值加1。
    return min(left_depth, right_depth) + 1

算法分析

  • 时间复杂度：O(N)
  • 空间复杂度：O(H)，H为树的高度
  • 核心技巧：递归分治

题目五：二叉树先序序列化和反序列化

问题描述

设计一个算法来序列化和反序列化二叉树。将树转换为字符串（序列化），再将字符串转换为树（反序列化）。

测试链接：https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/

序列化与反序列化
层序遍历反序列化

核心思想

序列化

使用先序遍历（根-左-右）将树递归地转换成字符串。空节点用特殊字符’#’表示，节点之间用’,’分隔。

反序列化

利用先序遍历的顺序，递归地重建树。字符串按’,’分割成列表，然后用一个迭代器顺序消费这些值来构建节点。

重要说明

二叉树可以通过先序、后序或者按层遍历的方式序列化和反序列化，但是无法通过中序遍历的方式实现序列化和反序列化，因为不同的两棵树可能得到同样的中序序列。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# 中序遍历的反面例子，比如如下两棵树
#         __2
#        /
#       1
#       和
#       1__
#          \
#           2
# 补足空位置的中序遍历结果都是{ null, 1, null, 2, null}

# 提交这个类
class Codec:
    def serialize(self, root):
        # 核心思想：使用先序遍历（根-左-右）将树递归地转换成字符串。
        # 空节点用特殊字符'#'表示，节点之间用','分隔。 #叫sharp
        res = [] #res是结果列表result
        self._f(root, res)
        return ",".join(res)

    def _f(self, root, res): # 递归函数求先序遍历
        if not root:
            res.append("#")
            return
        res.append(str(root.val))
        self._f(root.left, res)
        self._f(root.right, res)

    def deserialize(self, data):
        # 核心思想：利用先序遍历的顺序，递归地重建树。
        # 字符串按','分割成列表，然后用一个迭代器顺序消费这些值来构建节点。
        if not data:
            return None
        vals = iter(data.split(','))
        return self._g(vals)

    def _g(self, vals): # 递归函数求反序列化
        val = next(vals) # 迭代器，next是取下一个值，val是理论上是字符串，next能逐个取值
        if val == "#":
            return None
        
        # 先构建根节点，然后递归构建左子树，再递归构建右子树
        head = Code05_PreorderSerializeAndDeserialize.TreeNode(int(val))
        head.left = self._g(vals)
        head.right = self._g(vals)
        return head

算法分析

  • 时间复杂度：O(N)
  • 空间复杂度：O(N)
  • 核心技巧：先序遍历 + 迭代器

题目六：二叉树按层序列化和反序列化

问题描述

使用层序遍历的方式实现二叉树的序列化和反序列化。

测试链接：https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/

核心思想

序列化

使用广度优先搜索（BFS）进行层序遍历。队列中的每个节点，都将其左右子节点（即使是None）的信息加入结果字符串。

反序列化

同样使用BFS和队列来重建树。先创建根节点并入队，然后依次出队父节点，并从字符串值列表中读出左右子节点的信息进行构建和连接。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
# 提交这个类，补点思想即：把所有空节点也序列化/反序列化出来，不遗漏任何节点位置。
# 按层序列化
class Codec:
    def serialize(self, root):
        # 核心思想：使用广度优先搜索（BFS）进行层序遍历。
        # 队列中的每个节点，都将其左右子节点（即使是None）的信息加入结果字符串。
        if not root:
            return ""  # 空树直接返回空字符串
        res = []
        queue = deque([root])
        while queue:
            cur = queue.popleft()
            if cur:
                res.append(str(cur.val))  # 记录当前节点值
                queue.append(cur.left)    # 即使是None也加入队列，补点思想
                queue.append(cur.right)   # 即使是None也加入队列，补点思想
            else:
                res.append("#")  # 用'#'表示空节点，补点思想
        return ",".join(res)  # 用逗号连接成字符串

    def deserialize(self, data):
        # 核心思想：同样使用BFS和队列来重建树。
        # 先创建根节点并入队，然后依次出队父节点，并从字符串值列表中读出左右子节点的信息进行构建和连接。
        if not data:
            return None  # 空字符串返回空树
        nodes = data.split(',') # 字符串按逗号分割成列表
        root = self.generate(nodes[0])  # 构建根节点
        queue = deque([root])
        index = 1  # 指向下一个要处理的节点值在nodes中的位置
        while queue:
            parent = queue.popleft() #这个循环是按层从顶到下遍历的，parent是父节点
            if index < len(nodes):
                # 生成父节点的左孩子，补点思想
                parent.left = self.generate(nodes[index])
                index += 1
            if index < len(nodes):
                # 生成父节点的右孩子，补点思想
                parent.right = self.generate(nodes[index])
                index += 1
            # 只将非空子节点入队
            if parent.left:
                queue.append(parent.left)
            if parent.right:
                queue.append(parent.right)
        return root

    def generate(self, val):
        if val == "#":
            return None  # 空点返回None，补点思想
        return Code06_LevelorderSerializeAndDeserialize.TreeNode(int(val))  # 普通点返回节点对象

算法分析

  • 时间复杂度：O(N)
  • 空间复杂度：O(N)
  • 核心技巧：层序遍历 + 补点思想

题目七：利用先序与中序遍历序列构造二叉树

问题描述

根据一棵树的前序遍历与中序遍历构造二叉树。要求没有重复元素。

测试链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

先序+中序重构树
先序+中序重构树2

核心思想

递归分治。先序遍历的第一个元素是当前子树的根。在中序遍历中找到这个根，其左边的所有元素构成左子树，右边的所有元素构成右子树。根据左子树的元素数量，可以确定先序遍历中左右子树的范围，从而递归构建。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# 提交如下的方法
def buildTree(self, pre: List[int], tin: List[int]) -> Optional[TreeNode]:
    if not pre or not tin or len(pre) != len(tin):
        return None
    # 为了快速查找根节点在中序遍历中的位置，预处理成哈希表
    in_map = {val: i for i, val in enumerate(tin)}
    return self._f(pre, 0, len(pre) - 1, tin, 0, len(tin) - 1, in_map) #初始化方法

def _f(self, pre, l1, r1, tin, l2, r2, in_map):
    if l1 > r1:
        return None
    head = self.TreeNode(pre[l1])
    if l1 == r1: # 如果l1和r1相等，说明只有一个节点，直接返回head
        return head
    
    # k是根节点在中序遍历中的位置
    k = in_map[pre[l1]]
    # 左子树的节点数量
    left_size = k - l2
    
    # 递归构建左子树和右子树
    # pre : l1(........)[.......r1] -> l1是根, (l1+1...l1+left_size)是左子树, (...)是右子树
    # in  : (l2......)k[........r2] -> k是根, (l2...k-1)是左子树, [...]是右子树
    head.left = self._f(pre, l1 + 1, l1 + left_size, tin, l2, k - 1, in_map)
    head.right = self._f(pre, l1 + left_size + 1, r1, tin, k + 1, r2, in_map)
    return head

算法分析

  • 时间复杂度：O(N)
  • 空间复杂度：O(N)
  • 核心技巧：递归分治 + 哈希表优化

题目八：验证完全二叉树

问题描述

给定一个二叉树，确定它是否是一个完全二叉树。在一棵完全二叉树中，除了最后一层外，所有层都被完全填满，并且最后一层中的所有节点都要靠左。

测试链接：https://leetcode.cn/problems/check-completeness-of-a-binary-tree/

判断完全二叉树

核心思想

使用BFS进行层序遍历。一棵完全二叉树有两个特点：

  1. 任何节点不能只有右孩子没有左孩子
  2. 在层序遍历中，一旦遇到第一个孩子不双全的节点，之后遇到的所有节点都必须是叶子节点

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 提交以下的方法，实际上是一个又一个节点的bfs
def isCompleteTree(self, h: Optional[TreeNode]) -> bool:
    if not h:
        return True
    queue = deque([h])
    # 是否遇到过左右两个孩子不双全的节点
    leaf_stage = False
    while queue:
        node = queue.popleft()
        # case 1: 如果一个节点只有右孩子没有左孩子，必不是完全二叉树
        # case 2: 如果已经遇到了不双全的节点(进入leaf_stage)，后面又出现了孩子节点，也不是完全二叉树
        if (not node.left and node.right) or \
            (leaf_stage and (node.left or node.right)):
            return False
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
        
        # 一旦遇到孩子不双全的节点，就进入leaf_stage设为true，下一次循环中进行判断
        if not node.left or not node.right:
            leaf_stage = True
    return True

算法分析

  • 时间复杂度：O(N)
  • 空间复杂度：O(N)
  • 核心技巧：BFS + 状态标记

题目九：求完全二叉树的节点个数

问题描述

给出一个完全二叉树，求出该树的节点个数。要求时间复杂度低于O(N)。

测试链接：https://leetcode.cn/problems/count-complete-tree-nodes/

统计完全二叉树节点
统计完全二叉树节点2

核心思想

利用完全二叉树的性质进行优化。对于任意节点，其左子树和右子树中，至少有一个是满二叉树。通过比较左右子树的高度，可以判断出哪个是满二叉树，从而用公式 (2^h - 1) 快速计算其节点数，然后只需递归计算另一半子树。每次递归都会下降一层，所以递归深度最多是 O(logN)，每次调用 _mostLeft 的时间复杂度是 O(logN)，这使得时间复杂度从O(N)降低到O((logN)^2)。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def countNodes(self, head: Optional[TreeNode]) -> int:
    if not head:
        return 0
    h = self._mostLeft(head, 1)  # 计算整棵树的高度
    return self._f(head, 1, h)

def _f(self, cur, level, h):
    """
    cur: 当前来到的节点
    level: 当前cur来到的节点在第几层
    h: 整棵树的高度
    返回: cur这棵子树上有多少节点
    """
    if level == h: # base case: 遍历到了最底层
        return 1
    
    # 如果右子树的最左路径能到达整棵树的最后一层
    if self._mostLeft(cur.right, level + 1) == h:
        # 说明cur的左子树是满二叉树，其节点数可以直接计算
        # 节点总数 = 左子树节点数(2^(h-level)-1) + 根节点(1) + 递归求右子树节点数
        # 合并后就是 (1 << (h - level)) + 递归求右子树
        return (1 << (h - level)) + self._f(cur.right, level + 1, h) #1 << n 表示将数字1向左移动n位
    else: #if else判断往左递归还是往右递归
        # 否则，说明cur的右子树是比左子树少一层的满二叉树
        # 节点总数 = 右子树节点数(2^(h-level-1)-1) + 根节点(1) + 递归求左子树节点数
        # 合并后就是 (1 << (h - level - 1)) + 递归求左子树
        return (1 << (h - level - 1)) + self._f(cur.left, level + 1, h)

def _mostLeft(self, cur, level):
    """
    当前节点是cur，并且它在level层
    返回从cur开始不停往左，能扎到几层
    """
    while cur:
        level += 1
        cur = cur.left
    return level - 1

算法分析

  • 时间复杂度：O((logN)²)
  • 空间复杂度：O(logN)
  • 核心技巧：完全二叉树性质 + 满二叉树公式

核心技巧总结

1. BFS层序遍历

1
2
3
4
5
6
7
8
9
10
11
# 标准BFS模板
queue = deque([root])
while queue:
    size = len(queue)  # 当前层节点数
    for _ in range(size):  # 处理当前层
        node = queue.popleft()
        # 处理当前节点
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

2. 树的递归

1
2
3
4
5
6
7
# 递归模板
def traverse(root):
    if not root:  # base case
        return
    # 处理当前节点
    traverse(root.left)   # 递归左子树
    traverse(root.right)  # 递归右子树

3. 完全二叉树编号

1
2
3
# 根节点编号为1
# 左子节点编号为 2*i
# 右子节点编号为 2*i + 1

4. 序列化技巧

1
2
3
# 先序序列化：根-左-右
# 层序序列化：逐层BFS + 补点
# 中序无法唯一确定树结构

复杂度分析总结

题目 时间复杂度 空间复杂度 核心算法
层序遍历 O(N) O(N) BFS
锯齿形遍历 O(N) O(N) BFS + 反转
最大宽度 O(N) O(N) BFS + 编号
最大/最小深度 O(N) O(H) 递归
先序序列化 O(N) O(N) 递归 + 迭代器
层序序列化 O(N) O(N) BFS + 补点
构造二叉树 O(N) O(N) 递归 + 哈希表
验证完全二叉树 O(N) O(N) BFS + 状态
完全二叉树节点数 O((logN)²) O(logN) 递归 + 性质

学习建议

  1. 掌握BFS和DFS：这是处理树问题的两大基本方法

  2. 理解递归本质：树的递归结构使得很多问题都可以用递归解决

  3. 灵活运用数据结构：

    • 队列（BFS）
    • 哈希表（快速查找）
    • 迭代器（序列化处理）

  4. 注意边界条件：

    • 空树处理
    • 叶子节点判断
    • 层级边界

  5. 理解树的性质：

    • 完全二叉树的特点
    • 满二叉树的节点公式
    • 不同遍历方式的特点

  6. 练习组合技巧：很多树的问题需要组合多种基础算法

通过掌握这些经典的二叉树算法，可以为后续学习更复杂的树型动态规划和高级树结构打下坚实的基础。

037【必备】二叉树高频题目-下-不含树型dp

初始化的二叉树类

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

题目一：普通二叉树上寻找两个节点的最近公共祖先

问题描述

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

测试链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/

普通二叉树查找最近共同祖先

核心思想

采用递归的方式深度优先搜索：

  1. 如果当前节点为空，或者等于p或q中的一个，那么它本身就是其子树中p或q的LCA
  2. 否则，递归地在左子树和右子树中寻找p和q
  3. 如果左右子树都返回了非空节点，说明p和q分别位于当前节点的两侧，当前节点就是LCA
  4. 如果只有一个子树返回了非空节点，说明p和q都在那个子树中，返回那个非空节点即可
  5. 如果左右子树都返回空，说明p和q都不在此子树中。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        """
        寻找最近公共祖先的核心函数
        采用递归的方式深度优先搜索
        """

        # 遇到空，或者p，或者q，直接返回
        # 这是递归的基准情况 (base case)
        if not root or root == p or root == q: # 如果root不空的话，这样从下往上会一直传p或者q
            return root

        # 在左子树和右子树中递归查找 p 和 q
        l = self.lowestCommonAncestor(root.left, p, q)
        r = self.lowestCommonAncestor(root.right, p, q)

        # 左树也搜到，右树也搜到，返回root
        # 这意味着p和q分别在root的左右两侧，root是它们的LCA
        if l and r:
            return root
        
        # 如果左右子树的搜索结果都为空，说明p,q不在此子树
        if not l and not r:
            return None
        
        # l和r一个为空，一个不为空
        # 返回不空的那个，这个非空节点要么是p或q本身，要么已经是p和q的LCA
        return l if l else r

算法分析

  • 时间复杂度：O(N)，最坏情况下需要遍历所有节点
  • 空间复杂度：O(H)，H为树的高度，递归栈的深度
  • 核心技巧：递归 + 分情况讨论

题目二：搜索二叉树上寻找两个节点的最近公共祖先

问题描述

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

测试链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/

搜索二叉树查找最近共同祖先

核心思想

利用BST的特性，可以高效地进行迭代查找：

  1. 从根节点开始遍历
  2. 如果p和q的值都小于当前节点的值，说明LCA必定在左子树，往左走
  3. 如果p和q的值都大于当前节点的值，说明LCA必定在右子树，往右走
  4. 如果当前节点的值在p和q的值之间（或者等于其中一个），那么当前节点就是第一个”分叉点”，即为LCA

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        """
        在二叉搜索树(BST)中寻找最近公共祖先
        利用BST的特性，可以高效地进行迭代查找
        """

        # 确定p和q节点值的范围
        min_val = min(p.val, q.val)
        max_val = max(p.val, q.val)

        # 循环遍历，直到找到LCA
        while root:
            # 如果当前节点的值大于p和q的最大值，说明LCA在左子树
            if root.val > max_val:
                root = root.left
            # 如果当前节点的值小于p和q的最小值，说明LCA在右子树
            elif root.val < min_val:
                root = root.right
            # 否则，当前节点的值在[min_val, max_val]之间，它就是LCA
            else:
                return root
        
        return None # 理论上在有效输入下不会到达这里

算法分析

  • 时间复杂度：O(H)，H为树的高度
  • 空间复杂度：O(1)
  • 核心技巧：利用BST性质 + 迭代

题目三：收集累加和等于aim的所有路径

问题描述

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

测试链接：https://leetcode.cn/problems/path-sum-ii/

dfs回溯的概念
dfs回溯的概念2

核心思想

使用DFS + 回溯的方法：

  1. 维护一个当前路径 path 和当前路径和 current_sum
  2. 深入遍历树，每经过一个节点，就将其加入 path，并更新 current_sum
  3. 当到达一个叶子节点时，检查 current_sum + cur.val是否等于目标值，如果是，将当前路径（包括叶子节点）的一个副本添加到最终结果 ans 中
  4. 遍历完一个节点的所有子树后，需要回溯，即将该节点从 path 中移除，以便返回到父节点继续搜索其他分支

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
from typing import List, Optional

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        """
        主函数，初始化结果列表和路径列表，并启动递归搜索
        """
        ans = []
        if root:
            path = []
            # 调用递归辅助函数 f
            self.f(root, targetSum, 0, path, ans) # 一开始sum=0，ans也是空列表，path也是空列表
        return ans

    def f(self, cur: TreeNode, aim: int, current_sum: int, path: List[int], ans: List[List[int]]):
        """
        递归辅助函数，用于深度优先搜索所有路径
        """  

        # 将当前节点值加入路径
        path.append(cur.val) 
        
        # 判断是否为叶节点
        is_leaf = cur.left is None and cur.right is None 
        
        if is_leaf:
            # 叶节点
            # 如果当前路径和加上叶节点的值等于目标值，则找到一个有效路径
            if current_sum + cur.val == aim: 
                # 将路径的副本添加到结果中
                # 必须是副本(path[:])，否则后续的回溯操作会影响已存入的结果
                ans.append(path[:])
        else:
            # 不是叶节点
            # 递归探索左子树
            if cur.left:
                self.f(cur.left, aim, current_sum + cur.val, path, ans)
            # 递归探索右子树
            if cur.right:
                self.f(cur.right, aim, current_sum + cur.val, path, ans)
        
        # 回溯步骤：当一个节点的左右子树都探索完毕后，
        # 将该节点从当前路径中移除，返回到其父节点的递归调用中。
        path.pop() # 用 path.pop() 把刚才加入的那个节点移除，恢复到进入递归前的状态

回溯不会死循环的原因

  1. 控制流是”递归调用”不是”循环依赖”：每次调用只会递归左子树、右子树各最多一次
  2. for/if 的次数是固定的：子树递归只发生在固定的分支中，不会因为pop重复触发
  3. pop 只是在撤销路径，不改变遍历指针：pop 修改的是 path 内容，用于恢复现场；并不改变 cur、cur.left、cur.right 的结构或递归栈帧。可以把它看作：DFS 到底（或到叶/路尽）后，撤销上一步选择，然后走兄弟分支；兄弟分支走完，再撤销并上返……直到根。整个过程单调“回退”栈帧，不可能形成死循环。这个调用栈帧的所有工作（检查/递归左右）都完成了，撤销现场后，自然结束返回到父调用。

算法分析

  • 时间复杂度：O(N²)，最坏情况下每条路径都需要复制
  • 空间复杂度：O(H)，H为树的高度
  • 核心技巧：DFS + 回溯 + 路径复制

题目四：验证平衡二叉树

问题描述

给定一个二叉树，判断它是否是高度平衡的二叉树。一个高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

测试链接：https://leetcode.cn/problems/balanced-binary-tree/

平衡二叉树概念

核心思想

使用后序遍历的思想：

  1. 要判断当前节点是否平衡，需要先知道其左右子树的高度
  2. 这天然地符合后序遍历的顺序（先左、再右、后根）
  3. 递归地计算左子树和右子树的高度
  4. 在计算完左右子树高度后，检查它们的高度差
  5. 使用一个实例变量来记录是否已发现不平衡，一旦发现不平衡，就将此标志设为False，后续的递归调用可以提前终止。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
from typing import Optional

class Solution:
    def __init__(self):
        # balance是实例变量，用于在递归调用中共享状态，所以能够实现全局变量的效果
        # 每次判断开始时，在主函数中将其重置为true
        self.balance = True

    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        """
        主函数，用于启动平衡性检查
        """
        # 重置平衡标志
        self.balance = True
        # 调用递归函数计算高度并检查平衡性
        self.height(root)
        return self.balance

    def height(self, cur: Optional[TreeNode]) -> int:
        """
        递归计算节点高度，并在此过程中检查平衡性
        """
        # 核心思想（后序遍历）：
        # 1. 要判断当前节点是否平衡，需要先知道其左右子树的高度。
        # 2. 这天然地符合后序遍历的顺序（先左、再右、后根）。
        # 3. 递归地计算左子树和右子树的高度。
        # 4. 在计算完左右子树高度后，检查它们的高度差。如果差值大于1，说明树不平衡。
        # 5. 使用一个全局或实例变量 `self.balance` 来记录是否已发现不平衡。
        #    一旦发现不平衡，就将此标志设为False，后续的递归调用可以提前终止。

        # 一旦发现不平衡，或者当前节点为空，返回0，后续计算已无意义或到达递归边界
        if not self.balance or cur is None:
            return 0
        
        # 递归计算左子树的高度
        lh = self.height(cur.left)
        # 递归计算右子树的高度
        rh = self.height(cur.right)
        
        # 检查左右子树的高度差
        if abs(lh - rh) > 1:
            # 如果高度差大于1，则标记为不平衡
            self.balance = False
        
        # 返回当前节点的高度，即左右子树中较高者的高度加1
        # 叶子节点的高度为 1，因为它的左右子树高度都是 0，返回 max(0, 0) + 1 = 1
        return max(lh, rh) + 1

算法分析

  • 时间复杂度：O(N)，每个节点访问一次
  • 空间复杂度：O(H)，H为树的高度
  • 核心技巧：后序遍历 + 全局状态

题目五：验证搜索二叉树

问题描述

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

测试链接：https://leetcode.cn/problems/validate-binary-search-tree/

判断搜索二叉树方法1
判断搜索二叉树方法2

核心思想

有两种实现方法：

方法一：中序遍历

一个有效的BST，其中序遍历的结果必然是一个严格递增的序列。

方法二：递归验证

对任意一个节点，它必须满足：

  1. 它的左子树是BST，且左子树所有节点的值都小于它自身的值
  2. 它的右子树是BST，且右子树所有节点的值都大于它自身的值

算法实现

方法一：迭代实现的中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def isValidBST1(self, head: Optional[TreeNode]) -> bool:
    """
    通过迭代方式进行中序遍历来验证BST。
    核心思想：
    一个有效的BST，其中序遍历的结果必然是一个严格递增的序列。
    因此，我们可以在遍历过程中，持续比较当前节点的值和前一个节点的值。
    如果发现当前节点值小于或等于前一个节点值，那么它就不是一个BST。
    """
    if not head:
        return True
    
    stack = []
    pre_node = None
    
    # 使用cur指针和栈来模拟递归的中序遍历
    cur = head
    while stack or cur:
        if cur:
            # 一直向左，将路径上的节点入栈
            stack.append(cur)
            cur = cur.left
        else:
            # 左边到头了，从栈中弹出一个节点，这个就是中序遍历的当前节点
            cur = stack.pop()
            
            # 检查中序遍历的有序性，pre_node是当前节点的前一个节点
            if pre_node is not None and pre_node.val >= cur.val:
                return False
            
            # 更新前一个节点，然后转向右子树
            pre_node = cur
            cur = cur.right
            
    return True

方法二：递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
def __init__(self):
    # 实例变量，用于在递归调用中传递子树的最小值和最大值
    self.min_val = float('inf')
    self.max_val = float('-inf')

def isValidBST2(self, head: Optional[TreeNode]) -> bool:
    """
    通过递归方式验证BST。
    核心思想：
    对任意一个节点，它必须满足：
    1. 它的左子树是BST，且左子树所有节点的值都小于它自身的值。
    2. 它的右子树是BST，且右子树所有节点的值都大于它自身的值。
    这个过程可以通过后序遍历，在返回时收集子树的信息（是否为BST，最大值，最小值）来完成。
    """
    # Base case是 head is None，即空树的情况，
    if head is None:
        # 基准情况：空树是有效的BST
        # 初始化min和max，确保不影响上层计算
        self.min_val = float('inf')
        self.max_val = float('-inf')
        return True

    # 递归检查左子树是不是有效的BST
    is_left_ok = self.isValidBST2(head.left)
    l_min = self.min_val  # 保存左子树的最小值
    l_max = self.max_val  # 保存左子树的最大值
    
    # 递归检查右子树是不是有效的BST
    is_right_ok = self.isValidBST2(head.right)
    r_min = self.min_val
    r_max = self.max_val
    
    # 更新当前树的min和max值
    self.min_val = min(l_min, r_min, head.val)
    self.max_val = max(l_max, r_max, head.val)
    
    # 综合判断当前节点是否满足BST的条件
    # 1. 左右子树本身都是BST (is_left_ok and is_right_ok)
    # 2. 左子树的最大值必须小于当前节点值 (l_max < head.val)
    # 3. 右子树的最小值必须大于当前节点值 (head.val < r_min)
    return is_left_ok and is_right_ok and l_max < head.val and head.val < r_min

算法分析

  • 时间复杂度：O(N)，每个节点访问一次
  • 空间复杂度：O(H)，H为树的高度
  • 核心技巧：中序遍历有序性 / 递归验证BST性质

题目六：修剪搜索二叉树

问题描述

给你二叉搜索树的根节点 root ，同时给定最小边界 low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在 [low, high] 中。

测试链接：https://leetcode.cn/problems/trim-a-binary-search-tree/

修剪搜索二叉树

核心思想

利用BST的性质进行递归：

  1. 如果 cur.val < low，那么 cur 和它的整个左子树都应该被删除，修剪后的树必定在右子树中
  2. 如果 cur.val > high，那么 cur 和它的整个右子树都应该被删除，修剪后的树必定在左子树中
  3. 如果 low <= cur.val <= high，那么当前节点应该被保留，继续递归地修剪左右子树

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from typing import Optional

class Solution:
    def trimBST(self, cur: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
        """
        递归地修剪二叉搜索树。
        核心思想：
        利用BST的性质进行递归。对于当前节点 `cur`：
        1. 如果 `cur.val < low`，那么 `cur` 和它的整个左子树都应该被删除。
           修剪后的树必定在 `cur` 的右子树中，因此我们返回对右子树的修剪结果。
        2. 如果 `cur.val > high`，那么 `cur` 和它的整个右子树都应该被删除。
           修剪后的树必定在 `cur` 的左子树中，因此我们返回对左子树的修剪结果。
        3. 如果 `low <= cur.val <= high`，那么 `cur` 节点应该被保留。
           我们继续递归地修剪它的左子树和右子树，并将返回的结果作为 `cur` 新的左、右孩子。
           最后返回 `cur` 本身。
        """
        # base case是 cur is None，即空树的情况，返回None
        if cur is None:
            return None
        
        # 当前节点值太小，应该在右子树中寻找有效部分
        if cur.val < low:
            return self.trimBST(cur.right, low, high)
        
        # 当前节点值太大，应该在左子树中寻找有效部分
        if cur.val > high:
            return self.trimBST(cur.left, low, high)
        
        # 当前节点在 [low, high] 范围内，保留该节点
        # 然后递归地处理它的左子树和右子树
        cur.left = self.trimBST(cur.left, low, high)
        cur.right = self.trimBST(cur.right, low, high)
        
        # 返回处理后的当前节点
        return cur

算法分析

  • 时间复杂度：O(N)，最坏情况下访问所有节点
  • 空间复杂度：O(H)，H为树的高度
  • 核心技巧：利用BST性质 + 递归修剪

题目七：二叉树打家劫舍问题

问题描述

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为”根”。除了”根”之外，每栋房子有且只有一个”父”房子与之相连。一番侦察之后，聪明的小偷意识到”这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。计算在不触动警报的前提下，小偷一晚能够盗取的最高金额。

测试链接：https://leetcode.cn/problems/house-robber-iii/

打家劫舍问题

核心思想

树形DP问题。对于任意一个节点，我们考虑两种情况：

  1. 偷当前节点：那么它的左右孩子节点都不能偷
  2. 不偷当前节点：那么它的左右孩子可以偷也可以不偷，取两者中的较大值

通过后序遍历，我们可以先计算出左右子树的结果，再用来推导当前节点的结果。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
from typing import Optional

class Solution:
    def __init__(self):
        # 实例变量，用于在递归中保存子问题的解
        # yes: 表示在X子树中，偷头节点的情况下能获得的最大收益
        # no: 表示在X子树中，不偷头节点的情况下能获得的最大收益
        self.yes = 0
        self.no = 0

    def rob(self, root: Optional[TreeNode]) -> int:
        """
        主函数，启动递归计算
        """
        self.f(root)
        return max(self.yes, self.no)

    def f(self, root: Optional[TreeNode]):
        """
        递归函数，采用后序遍历计算以root为根的子树的打劫收益
        核心思想 (树形DP):
        对于任意一个节点 `root`，我们考虑两种情况：
        1. 偷 `root` 节点：那么它的左右孩子节点都不能偷。
           最大收益 = `root.val` + 左子树不偷的最大收益 + 右子树不偷的最大收益。
        2. 不偷 `root` 节点：那么它的左右孩子可以偷也可以不偷，取两者中的较大值。
           最大收益 = max(偷左孩子，不偷左孩子) + max(偷右孩子，不偷右孩子)。
        
        通过后序遍历，我们可以先计算出左右子树的结果，再用来推导当前节点的结果。
        """
        if root is None:
            # 基准情况：空节点收益为0
            self.yes = 0
            self.no = 0
            return

        # 暂存当前节点的收益
        current_yes = root.val
        current_no = 0
        
        # 先递归处理左子树，再处理右子树
        self.f(root.left)
        # 此时 self.yes 和 self.no 是左子树的结果
        
        # 更新当前节点的收益：
        # 如果偷当前节点，则不能偷左孩子，所以加上左子树不偷的收益 no
        current_yes += self.no 
        # 如果不偷当前节点，则左孩子可偷可不偷，取最大值
        current_no += max(self.yes, self.no)
        
        # 递归处理右子树
        self.f(root.right)
        # 此时 self.yes 和 self.no 是右子树的结果
        
        # 再次更新当前节点的收益：
        # 加上右子树的贡献
        current_yes += self.no
        current_no += max(self.yes, self.no)
        
        # 将最终计算出的当前节点的结果，存回实例变量，供上层调用使用
        self.yes = current_yes
        self.no = current_no

算法分析

  • 时间复杂度：O(N)，每个节点访问一次
  • 空间复杂度：O(H)，H为树的高度
  • 核心技巧：树形DP + 后序遍历

核心技巧总结

1. LCA问题模板

1
2
3
4
5
6
7
8
9
10
def lowestCommonAncestor(self, root, p, q):
    if not root or 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

2. 路径搜索 + 回溯模板

1
2
3
4
5
6
7
8
9
10
11
def dfs(node, path, target):
    path.append(node.val)  # 选择
    
    if is_leaf(node):
        if meets_condition():
            result.append(path[:])  # 记录答案
    else:
        dfs(node.left, path, target)   # 递归
        dfs(node.right, path, target)  # 递归
    
    path.pop()  # 撤销选择（回溯）

3. BST性质利用

1
2
3
# BST中序遍历是有序的
# BST搜索可以利用大小关系剪枝
# BST的LCA在分叉点

4. 树形DP模板

1
2
3
4
5
6
7
8
9
10
11
12
def tree_dp(node):
    if not node:
        return base_case
    
    # 后序遍历：先处理子树
    left_result = tree_dp(node.left)
    right_result = tree_dp(node.right)
    
    # 根据子树结果计算当前节点结果
    current_result = combine(node.val, left_result, right_result)
    
    return current_result

复杂度分析总结

题目 时间复杂度 空间复杂度 核心算法
普通二叉树LCA O(N) O(H) 递归DFS
BST的LCA O(H) O(1) 利用BST性质
路径和问题 O(N²) O(H) DFS + 回溯
验证平衡二叉树 O(N) O(H) 后序遍历
验证BST O(N) O(H) 中序遍历/递归
修剪BST O(N) O(H) 递归修剪
打家劫舍III O(N) O(H) 树形DP

学习建议

  1. 掌握LCA问题：这是树算法中的经典问题，有多种解法和应用

  2. 理解BST性质：

    • 中序遍历有序
    • 可以利用大小关系进行搜索优化
    • 左子树 < 根 < 右子树

  3. 掌握回溯模板：

    • 做选择 → 递归 → 撤销选择
    • 注意保存结果时要使用副本

  4. 理解树形DP：

    • 后序遍历获取子树信息
    • 根据子树状态计算当前状态
    • 状态定义要考虑所有可能情况

  5. 注意边界条件：

    • 空节点处理
    • 叶子节点判断
    • 单节点情况

  6. 练习状态管理：

    • 实例变量在递归中的使用
    • 多个状态的传递和更新

通过掌握这些经典的二叉树问题，可以深入理解树的递归性质，为学习更高级的树算法和动态规划打下基础。这些问题模式在实际编程中经常出现，是算法面试的重点内容。