letecode [111] - Minimum Depth of Binary Tree

发布时间：2020-12-14 04:44:43 所属栏目：大数据来源：网络整理

导读：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. Note: A leaf is a node with no children. Example: Given binary tree [3,9,20,null

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.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,15,7],

??? 3
?? /
? 9? 20
??? /?
?? 15?? 7

return its minimum depth = 2.

题目大意：

　　给定二叉树，计算它从根节点到某个叶节点的最小路径（即节点数）。

理? 解：

　　自己的思想是：从根节点开始，往下访问子节点，找到第一个叶节点，作为当前最小深度。后面遍历其他子树的时候，大于最小深度的子树就剪枝，小于就更新最小深度。实现的时候有点很奇怪的问题，暂时没调试出来。

　　看了别人的思想。这个真的很棒。用队列辅助层次遍历，当访问的节点的左右子树均为空时，则当前节点为叶节点，返回当前层数即可。

代码 C++：

/**
?* Definition for a binary tree node.
?* struct TreeNode {
?*???? int val;
?*???? TreeNode *left;
?*???? TreeNode *right;
?*???? TreeNode(int x) : val(x),left(NULL),right(NULL) {}
?* };
?*/
class Solution {
public:
??? int minDepth(TreeNode* root) {
??????? if(root==NULL) return 0;
??????? if(root->left==NULL && root->right==NULL) return 1;
??????? queue<TreeNode*> q;
??????? q.push(root);
??????? int size;
??????? int level = 0;
??????? while(!q.empty()){
??????????? size = q.size();
??????????? level++;
??????????? while(size>0){
??????????????? TreeNode* node = q.front();
??????????????? q.pop();
??????????????? if(node->left==NULL && node->right==NULL)
??????????????????? return level;
??????????????? if(node->left!=NULL){
??????????????????? q.push(node->left);
??????????????? }
??????????????? if(node->right!=NULL){
??????????????????? q.push(node->right);
??????????????? }
??????????????? size--;
??????????? }
??????? }
??????? return level;
??????? 
??? }
};

运行结果：

　　执行用时 : 20 ms　　内存消耗 :?19.7 MB

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!