[leetcode]: 111. Minimum Depth of Binary Tree

爱被打了一巴掌 2022-06-14 19:54 294阅读 0赞

1.题目

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.
求一棵二叉树的最小深度。
最小深度的定义为根节点到叶子节点的最小距离

2.分析

广度优先遍历，BFS。
相当于从根节点开始，一层一层往下遍历，当遍历到第一个叶子节点时，所得到的深度是最小的。

3.代码

BFS

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == NULL)
            return 0;
        queue<pair<TreeNode*,int>> nodes;
        nodes.push(make_pair(root, 1));
        int depth = 0;
        while (!nodes.empty()) {
            TreeNode* node = nodes.front().first;
            depth = nodes.front().second;
            nodes.pop();
            if (node->left)
                nodes.push(make_pair(node->left, depth + 1));
            if (node->right)
                nodes.push(make_pair(node->right, depth + 1));
            if (!node->left && !node->right)//叶子节点
                return depth;
        }
    }
};