最小深度,最小深度是指树的根节点到最近叶子结点的最短路径上的数量"/>
LeetCode 的 C++ 实现(一) :求给定二叉树的最小深度,最小深度是指树的根节点到最近叶子结点的最短路径上的数量
题目描述
求给定二叉树的最小深度。最小深度是指树的根结点到最近叶子结点的最短路径上结点的数量。
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.
非递归
基本思路:从题目可以得到,最小深度的概念可以转换到二叉树的层数,那题目就转换到求二叉树的层数,非递归思路的话,借助队列来实现
从root开始先将当前层入队,该层入完后,遍历队列,同时将其叶子节点(既下一层)入队,这样既完成了对当前层的遍历查询也完成了下一层入队,在遍历时发现,该节点是叶子节点的话,证明已经找到最小的二叉树层数,返回即可
class Solution {
public:int run(TreeNode *root) {queue<TreeNode*> NowLevel;if(!root)return 0;if(!root->left && !root->right)return 1;int level = 1;NowLevel.push(root);while(!NowLevel.empty()){int levelsize = NowLevel.size();for(int i = 0 ; i < levelsize;i++){TreeNode* queFront = NowLevel.front();NowLevel.pop();if(!queFront->left && !queFront->right)return level;else{if(queFront->left)NowLevel.push(queFront->left);if(queFront->right)NowLevel.push(queFront->right); } }level++;} }
};
递归
class Solution {
public:int run(TreeNode *root) {if(!root)return 0;int DepthL = run(root->left);int DepthR = run(root->right);if(DepthL == 0 || DepthR == 0 )return 1 + DepthL + DepthR ;return 1 + min(DepthL , DepthR);}
};
更多推荐
LeetCode 的 C++ 实现(一) :求给定二叉树的最小深度,最小深度是指树的根节点到最近叶子结点的最短路径上的数量
发布评论