Minimum Depth of Binary Tree 题解
题目来源：https://leetcode.com/problems/minimum-depth-of-binary-tree/description/
Description
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Solution
class Solution {
private:
struct Task {
TreeNode *node;
int depth;
Task(TreeNode *n, int d) : node(n), depth(d) {}
};
public:
int minDepth(TreeNode* root) {
if (!root) {
return 0;
}
queue<Task> q;
q.push(Task(root, 1));
while (!q.empty()) {
Task task = q.front();
q.pop();
TreeNode *node = task.node;
if (node -> left == NULL && node -> right == NULL) {
return task.depth;
}
if (node -> left)
q.push(Task(node -> left, task.depth + 1));
if (node -> right)
q.push(Task(node -> right, task.depth + 1));
}
}
};解题描述
这道题题意是要求一棵二叉树的最小深度，解法是使用BFS，由于是自顶向下逐层扫描，得到的第一个叶子节点必定是深度最小的点，返回其高度即可。