求解二叉树最小深度：从根到叶子节点的最短路径

二叉树的最小深度是一个经典的计算机科学问题，主要涉及到树的遍历和数据结构的运用。在给定的二叉树中，我们需要找到从根节点到最近叶子节点的最短路径上的节点数量，这里的叶子节点指的是没有子节点的节点。题目提供了一个示例来帮助理解： 示例1： - 输入：二叉树的根节点是一个包含整数值的列表，如`root=[3,9,20,null,null,15,7]`。这意味着根节点值为3，其左子节点是9，右子节点是20，20的左子节点为空，20的右子节点也为空，而20的子树还有一个节点15和一个节点7。 - 输出：2。在这个例子中，最短路径是从根节点3到叶子节点7或15，共经过了2个节点（3和20）。 示例2： - 输入：`root=[2,null,3,null,4,null,5,null,6]`，这个二叉树没有完全展开，但我们可以看出它的结构。比如，节点2的右子节点是3，3的左右子节点分别是空和4，4没有子节点等。 - 输出：5。在这个例子中，最短路径是从根节点2到叶子节点6，需要经过5个节点（2, 3, 4, 5, 6）。 解决这个问题的常见方法是使用广度优先搜索（BFS），因为BFS总是优先遍历当前层的所有节点，然后进入下一层。我们使用一个队列来存储节点及其深度，初始化时将根节点放入队列，并设置深度为1。然后在循环中，不断取出队首节点，检查其子节点是否为空，如果为空则找到了叶子节点，返回当前深度；若不为空，则将子节点加入队列并更新深度。当队列为空时，说明没有找到叶子节点，此时返回0，代表树的高度为0。 参考的C++代码实现如下： ```cpp class Solution { public: int minDepth(TreeNode* root) { if (root == nullptr) { return 0; } queue<pair<TreeNode*, int>> que; que.emplace(root, 1); // 初始化根节点深度为1 while (!que.empty()) { TreeNode* node = que.front().first; int depth = que.front().second; que.pop(); if (node->left == nullptr && node->right == nullptr) { return depth; // 找到叶子节点，返回当前深度 } if (node->left != nullptr) { que.emplace(node->left, depth + 1); } if (node->right != nullptr) { que.emplace(node->right, depth + 1); } } return 0; // 如果没有找到叶子节点，返回树的高度为0 } }; ``` 总结来说，求解二叉树的最小深度问题涉及二叉树的结构理解和数据结构（队列）的应用，特别是广度优先搜索策略。通过逐层遍历并跟踪每个节点的深度，最终找到最近的叶子节点并返回其深度。这种方法的时间复杂度是O(n)，其中n是二叉树中的节点数。