当前位置：首页 > news >正文

【经典算法】二叉树最小深度详解：递归解法与可视化分析

news 2025/8/11 9:39:41

【经典算法】二叉树最小深度详解：递归解法与可视化分析

📌 简介

本文详细讲解如何求解二叉树的最小深度，涵盖二叉树基础、题目解析、递归解法、可视化分析及完整代码实现。通过清晰的示例和递归调用栈分析，帮助读者深入理解算法逻辑，掌握如何在实际项目中调用类方法解决问题。

📚 目录

🌳 二叉树介绍
📝 题目解析
🛠️ 解决方法
🔄 递归介绍与可视化分析
🔧 类的应用与调用方法
📊 总结

🌳 二叉树介绍

二叉树是一种每个节点最多有两个子节点（左子节点和右子节点）的树结构。常见术语：

根节点（Root）：树的顶层节点。
叶子节点（Leaf）：没有子节点的节点。
深度（Depth）：从根节点到某节点的路径长度。

示例二叉树：

        1/ \2   3/ \4   5

📝 题目解析

问题描述

给定一个二叉树，求其最小深度（从根节点到最近叶子节点的最短路径上的节点数）。

关键点

最小深度必须到叶子节点（即没有子节点的节点）。
若某节点只有一个子节点，不能直接取最小值（需继续向下查找）。

示例：

        1/2/3

最小深度为 3（路径 1 → 2 → 3），而非 1（右子树为空，不能直接返回 1）。

🛠️ 解决方法

递归思路

终止条件：当前节点为空时，返回 0。
递归计算左右子树深度：
- leftDepth = run(root->left)
- rightDepth = run(root->right)
分情况处理：
- 左右子树均非空：返回 min(leftDepth, rightDepth) + 1。
- 至少一个子树为空：返回 leftDepth + rightDepth + 1（避免忽略非空子树）。

代码实现

class Solution {
public:int run(TreeNode* root) {if (!root) return 0;int leftDepth = run(root->left);int rightDepth = run(root->right);if (leftDepth == 0 || rightDepth == 0) {return leftDepth + rightDepth + 1;}return min(leftDepth, rightDepth) + 1;}
};

🔄 递归介绍与可视化分析

递归调用栈示例

以二叉树 [1, 2, 3, 4, 5] 为例：

        1/ \2   3/ \4   5

递归过程：

run(1) → 调用 run(2) 和 run(3)。
run(2) → 调用 run(4) 和 run(5)（均返回 1）。
run(2) 返回 min(1, 1) + 1 = 2。
run(3) 是叶子节点，返回 1。
run(1) 返回 min(2, 1) + 1 = 2。

可视化表格

递归调用	`leftDepth`	`rightDepth`	返回值
`run(4)`	0	0	1
`run(5)`	0	0	1
`run(2)`	1	1	2
`run(3)`	0	0	1
`run(1)`	2	1	2

🔧 类的应用与调用方法

调用步骤

构建二叉树：手动创建节点并连接。
实例化 Solution 类：调用 run 方法。

示例代码：

int main() {// 构建二叉树 [1, 2, 3, 4, 5]TreeNode* root = new TreeNode(1);root->left = new TreeNode(2);root->right = new TreeNode(3);root->left->left = new TreeNode(4);root->left->right = new TreeNode(5);Solution solution;cout << "最小深度: " << solution.run(root) << endl; // 输出 2return 0;
}