首页 > 代码库 > leetcode第一刷_Minimum Depth of Binary Tree
leetcode第一刷_Minimum Depth of Binary Tree
非常easy的题目。只是还是认为要说一下。
最小深度。非常快想到bfs,层序遍历嘛。本科的时候实在是没写过多少代码,一開始竟然想不到怎么保存一层的信息。后来想到能够压入一个特殊的对象,每次到达这个对象就知道是一层了。我用的是空指针。认为这个适用性还是不错的。一层的节点入队结束后,应该压入一个NULL。当一层的节点都处理完。遇到NULL的时候,要在队列尾部再入队一个NULL,这是后一层的分界线嘛。
昨天在还有一道题上看到了还有一种做法。用一个数据结构vector<set<*> >(2)。当然vector里面包裹的是什么结构体并不重要,仅仅要能够高速的压入和顺序訪问就可以。vector的维度是二维的,保存当前层和上一层的对象。然后用两个相互排斥int值cur和pre来保存正在訪问和上一次訪问的vector,每一次遍历,扫描pre层。发现的节点增加到cur层,下次循环时,交换一下。
我认为这是一种非常好的思路,尽管用在普通的层序遍历上有杀鸡用牛刀了。
class Solution { public: int minDepth(TreeNode *root) { if(root == NULL) return 0; int res = 1; queue<TreeNode*> ceng; TreeNode *pNode; ceng.push(root); ceng.push(NULL); while(!ceng.empty()){ if(ceng.front() == NULL){ res++; ceng.pop(); ceng.push(NULL); } pNode = ceng.front(); ceng.pop(); if(!pNode->left&&!pNode->right) return res; if(pNode->left) ceng.push(pNode->left); if(pNode->right) ceng.push(pNode->right); } return res; } };
leetcode第一刷_Minimum Depth of Binary Tree
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。