[Leetcode] Minimum Depth of Binary Tree

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，由于是自顶向下逐层扫描，得到的第一个叶子节点必定是深度最小的点，返回其高度即可。