二叉树题解模版

Posted on 2023-10-11 Edited on 2025-10-12 In Fundamental , Algorithm

什么是二叉树？

二叉树是一种树形数据结构，每个节点最多有两个子节点，通常称为左子节点和右子节点。

常见的二叉树类型

完全二叉树：除了最后一层，其他层的节点都是满的，最后一层的节点都靠左排列。堆就是用完全二叉树实现的。
满二叉树：每一层的节点数都达到最大值，即每层都是满的。如果深度为 k，则有 2^k - 1 个节点。
二叉搜索树（BST）：对于任意节点，左子树的所有节点值都小于该节点值，右子树的所有节点值都大于该节点值。这个性质使得 BST 的查找、插入、删除操作都很高效。
平衡二叉树：任意节点的左右子树高度差不超过 1。常见的实现有 AVL 树和红黑树，用于保证树的操作时间复杂度。

二叉树的表示和构建

节点定义

在 LeetCode 和大多数面试中，二叉树节点的定义都是标准的：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

手动构建二叉树

面试或调试时，我们经常需要手动构建测试用例。最直接的方式是逐个创建节点：

# 构建这样的树：
#     1
#    / \
#   2   3
#  / \
# 4   5

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

这种方式很直观，但对于稍大一点的树就显得繁琐。

从列表构建二叉树

LeetCode 上的题目通常用列表表示二叉树，比如 [1,2,3,null,null,4,5]。这是层次遍历的表示方式，null 表示空节点。从层次遍历的表示构建二叉树如下：

from collections import deque

def build_tree(values):
    """从列表构建二叉树（层次遍历顺序）"""
    if not values:
        return None

    root = TreeNode(values[0])
    queue = deque([root])
    i = 1

    while queue and i < len(values):
        node = queue.popleft()

        # 处理左子节点
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1

        # 处理右子节点
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1

    return root

# 使用示例
root = build_tree([1, 2, 3, None, None, 4, 5])

二叉树解题核心思想

信息从哪里来？（自顶向下还是自底向上）
信息如何传递？（通过参数还是返回值）
什么时候更新答案？（遍历过程中还是递归返回时）

根据这三个维度，可以总结出几种常见的解题模板。

模板一：自顶向下遍历

适用场景

当问题需要从根节点向下传递信息时使用。通常的特征是：

答案与”从根到当前节点的路径”有关
需要记录路径上的某些统计信息（和、最大值、最小值等）
涉及祖先和后代节点的关系

典型例题：

Path Sum 系列
Binary Tree Paths
Maximum Difference Between Node and Ancestor

代码框架

class Solution:
    def solve(self, root):
        # 如果需要全局结果变量
        self.result = initial_value
        self.dfs(root, initial_path_info)
        return self.result

    def dfs(self, node, path_info):
        """
        参数说明：
        node: 当前节点
        path_info: 从根到当前节点的路径信息
        """
        # 终止条件
        if not node:
            return

        # 使用路径信息处理当前节点
        current_result = process(node.val, path_info)
        self.result = update(self.result, current_result)

        # 更新路径信息
        new_path_info = update_path_info(path_info, node.val)

        # 递归处理子树
        self.dfs(node.left, new_path_info)
        self.dfs(node.right, new_path_info)

        # 如果path_info是可变对象，这里需要回溯
        # backtrack(path_info)

实例：Maximum Difference Between Node and Ancestor

这道题要求找出树中任意节点与其祖先节点的最大差值。思路是在遍历过程中维护路径上的最大值和最小值。

class Solution:
    def maxAncestorDiff(self, root):
        return self.dfs(root, root.val, root.val)

    def dfs(self, node, path_max, path_min):
        if not node:
            return path_max - path_min

        # 更新路径的最大最小值
        path_max = max(path_max, node.val)
        path_min = min(path_min, node.val)

        # 递归子树
        left = self.dfs(node.left, path_max, path_min)
        right = self.dfs(node.right, path_max, path_min)

        return max(left, right)

关键点：

通过参数向下传递路径上的最大最小值
在叶子节点返回当前路径的差值
递归过程中取所有路径的最大值

实例：Path Sum

判断是否存在从根到叶子的路径，使得路径和等于目标值。

class Solution:
    def hasPathSum(self, root, targetSum):
        if not root:
            return False
        return self.dfs(root, 0, targetSum)

    def dfs(self, node, path_sum, target):
        if not node:
            return False

        path_sum += node.val

        # 叶子节点，检查路径和
        if not node.left and not node.right:
            return path_sum == target

        # 只要有一条路径满足就返回True
        return (self.dfs(node.left, path_sum, target) or
                self.dfs(node.right, path_sum, target))

实例：Binary Tree Paths

返回所有从根到叶子的路径。需要注意回溯的使用。

class Solution:
    def binaryTreePaths(self, root):
        result = []

        def dfs(node, path):
            if not node:
                return

            path.append(str(node.val))

            if not node.left and not node.right:
                result.append('->'.join(path))
            else:
                dfs(node.left, path)
                dfs(node.right, path)

            # 回溯：移除当前节点
            path.pop()

        dfs(root, [])
        return result

模板二：自底向上递归

适用场景

当需要利用子树的信息来计算当前节点的答案时使用。特征包括：

需要先知道左右子树的某些统计信息
问题可以分解为子问题
典型的”后序遍历”思想

典型例题：

Maximum Depth of Binary Tree
Balanced Binary Tree
Diameter of Binary Tree
Binary Tree Maximum Path Sum

代码框架

class Solution:
    def solve(self, root):
        self.result = initial_value
        self.dfs(root)
        return self.result

    def dfs(self, node):
        """
        返回值：当前子树的某种统计信息
        """
        # 终止条件
        if not node:
            return base_case

        # 先递归获取子树信息（后序遍历）
        left_info = self.dfs(node.left)
        right_info = self.dfs(node.right)

        # 使用子树信息处理当前节点
        current_info = compute(node.val, left_info, right_info)

        # 更新全局答案（如果需要）
        self.result = update(self.result, current_info)

        # 返回给父节点的信息
        return info_for_parent(current_info)

实例：Maximum Depth

最基础的自底向上问题。

class Solution:
    def maxDepth(self, root):
        if not root:
            return 0

        left_depth = self.maxDepth(root.left)
        right_depth = self.maxDepth(root.right)

        return max(left_depth, right_depth) + 1

实例：Binary Tree Maximum Path Sum

这是一道 Hard 题，但用自底向上的思路就很清晰。关键在于区分”返回给父节点的值”和”全局最大值”。

class Solution:
    def maxPathSum(self, root):
        self.max_sum = float('-inf')

        def dfs(node):
            if not node:
                return 0

            # 子树的最大贡献（负数不要）
            left_gain = max(dfs(node.left), 0)
            right_gain = max(dfs(node.right), 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

核心思想：

全局答案可以是”左子路径 + 根 + 右子路径”
但返回给父节点时只能选择一边

实例：Diameter of Binary Tree

直径是任意两节点间最长路径。

class Solution:
    def diameterOfBinaryTree(self, root):
        self.diameter = 0

        def dfs(node):
            if not node:
                return 0

            left_depth = dfs(node.left)
            right_depth = dfs(node.right)

            # 经过当前节点的最长路径
            self.diameter = max(self.diameter, left_depth + right_depth)

            # 返回高度
            return max(left_depth, right_depth) + 1

        dfs(root)
        return self.diameter

模板三：层次遍历（BFS）

适用场景

当需要按层处理节点时使用：

需要知道节点所在的层级
每层要做特殊处理
锯齿形遍历等变种

典型例题：

Binary Tree Level Order Traversal
Binary Tree Zigzag Level Order Traversal
Binary Tree Right Side View
Average of Levels in Binary Tree

代码框架

from collections import deque

class Solution:
    def levelOrder(self, root):
        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

实例：Binary Tree Zigzag Level Order Traversal

class Solution:
    def zigzagLevelOrder(self, root):
        if not root:
            return []

        result = []
        queue = deque([root])
        left_to_right = True

        while queue:
            level_size = len(queue)
            current_level = deque()

            for _ in range(level_size):
                node = queue.popleft()

                if left_to_right:
                    current_level.append(node.val)
                else:
                    current_level.appendleft(node.val)

                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            result.append(list(current_level))
            left_to_right = not left_to_right

        return result

实例：Binary Tree Right Side View

返回从右侧看到的节点值。

class Solution:
    def rightSideView(self, root):
        if not root:
            return []

        result = []
        queue = deque([root])

        while queue:
            level_size = len(queue)

            for i in range(level_size):
                node = queue.popleft()

                # 每层最后一个节点
                if i == level_size - 1:
                    result.append(node.val)

                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

        return result

模板四：前序遍历

适用场景

需要先访问根节点的场景：

构建树
序列化和反序列化
某些特定的树的遍历需求

代码框架

class Solution:
    # 递归实现
    def preorderTraversal(self, root):
        result = []

        def dfs(node):
            if not node:
                return

            result.append(node.val)
            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return result

    # 迭代实现（面试常考）
    def preorderTraversal_iterative(self, root):
        if not root:
            return []

        result = []
        stack = [root]

        while stack:
            node = stack.pop()
            result.append(node.val)

            # 先右后左（栈的特性）
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)

        return result

模板五：中序遍历

适用场景

这个模板主要用于 BST 相关问题，因为中序遍历 BST 会得到有序序列。

典型例题：

Validate Binary Search Tree
Kth Smallest Element in a BST
Binary Search Tree Iterator

代码框架

class Solution:
    # 递归实现
    def inorderTraversal(self, root):
        result = []

        def dfs(node):
            if not node:
                return

            dfs(node.left)
            result.append(node.val)
            dfs(node.right)

        dfs(root)
        return result

    # 迭代实现（重要）
    def inorderTraversal_iterative(self, root):
        result = []
        stack = []
        current = root

        while current or stack:
            # 一路向左
            while current:
                stack.append(current)
                current = current.left

            # 处理当前节点
            current = stack.pop()
            result.append(current.val)

            # 转向右子树
            current = current.right

        return result

实例：Kth Smallest Element in a BST

class Solution:
    def kthSmallest(self, root, k):
        self.count = 0
        self.result = None

        def inorder(node):
            if not node or self.result is not None:
                return

            inorder(node.left)

            self.count += 1
            if self.count == k:
                self.result = node.val
                return

            inorder(node.right)

        inorder(root)
        return self.result

模板六：后序遍历

适用场景

需要先处理子节点再处理根节点的场景：

删除节点
计算表达式树
某些需要”自底向上”信息的场景

代码框架

class Solution:
    # 递归实现
    def postorderTraversal(self, root):
        result = []

        def dfs(node):
            if not node:
                return

            dfs(node.left)
            dfs(node.right)
            result.append(node.val)

        dfs(root)
        return result

    # 迭代实现
    def postorderTraversal_iterative(self, root):
        if not root:
            return []

        result = []
        stack = [root]

        while stack:
            node = stack.pop()
            result.append(node.val)

            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)

        return result[::-1]

练习技巧

如何选择合适的模板

graph TD
    A[遇到二叉树问题] --> B{是否需要层级信息?}
    B -- 是 --> BFS[层次遍历（BFS）]
    B -- 否 --> C{是否是 BST?}
    C -- 是 --> INORDER[中序遍历（BST）]
    C -- 否 --> D{信息流向?}
    D -- 子树信息（自底向上） --> POSTORDER[后序遍历/自底向上]
    D -- 路径信息（自顶向下） --> TOPDOWN[自顶向下 DFS]
    D -- 其他 --> E{遍历顺序?}
    E -- 先访问根 --> PREORDER[前序遍历]
    E -- 先访问子节点 --> POSTORDER2[后序遍历]

自顶向下 + 回溯

适用于需要记录完整路径的场景。

def pathSum(root, target):
    result = []

    def dfs(node, path, path_sum):
        if not node:
            return

        path.append(node.val)
        path_sum += node.val

        if not node.left and not node.right and path_sum == target:
            result.append(path[:])

        dfs(node.left, path, path_sum)
        dfs(node.right, path, path_sum)

        # 回溯
        path.pop()

    dfs(root, [], 0)
    return result

自底向上 + 全局变量

适用于需要记录全局最优解的场景。

class Solution:
    def longestUnivaluePath(self, root):
        self.max_length = 0

        def dfs(node):
            if not node:
                return 0

            left_len = dfs(node.left)
            right_len = dfs(node.right)

            left = left_len + 1 if node.left and node.left.val == node.val else 0
            right = right_len + 1 if node.right and node.right.val == node.val else 0

            self.max_length = max(self.max_length, left + right)

            return max(left, right)

        dfs(root)
        return self.max_length

DFS + 剪枝

在搜索过程中提前排除不可能的分支。

def isValidBST(root):
    def dfs(node, min_val, max_val):
        if not node:
            return True

        if node.val <= min_val or node.val >= max_val:
            return False

        return (dfs(node.left, min_val, node.val) and
                dfs(node.right, node.val, max_val))

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

解题通用步骤

识别题目类型（路径、子树、层级、BST 等）
确定信息流向（自顶向下、自底向上、层序）
设计递归函数签名（参数和返回值）
处理边界条件（空节点、叶子节点）
实现核心逻辑
用小例子验证

什么是二叉树？

常见的二叉树类型

二叉树的表示和构建

节点定义

手动构建二叉树

从列表构建二叉树

二叉树解题核心思想

模板一：自顶向下遍历

适用场景

代码框架

实例：Maximum Difference Between Node and Ancestor

实例：Path Sum

实例：Binary Tree Paths

模板二：自底向上递归

适用场景

代码框架

实例：Maximum Depth

实例：Binary Tree Maximum Path Sum

实例：Diameter of Binary Tree

模板三：层次遍历（BFS）

适用场景

代码框架

实例：Binary Tree Zigzag Level Order Traversal

实例：Binary Tree Right Side View

模板四：前序遍历

适用场景

代码框架

模板五：中序遍历

适用场景

代码框架

实例：Kth Smallest Element in a BST

模板六：后序遍历

适用场景

代码框架

练习技巧

如何选择合适的模板

自顶向下 + 回溯

自底向上 + 全局变量

DFS + 剪枝

解题通用步骤

推荐练习