【题目】
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.
【分析】
类似于:LeetCode之Maximum Depth of Binary Tree
【代码】
/*********************************
* 日期:2014-12-30
* 作者:SJF0115
* 题目: 111.Minimum Depth of Binary Tree
* 来源:https://oj.leetcode.com/problems/minimum-depth-of-binary-tree/
* 结果:AC
* 来源:LeetCode
* 总结:
**********************************/
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// 二叉树节点
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
// 左子树最小高度
int leftHeight = minDepth(root->left);
// 右子树最小高度
int rightHeight = minDepth(root->right);
// 只有左子树或者只有右子树或者左右子树都没有
if(leftHeight == 0 || rightHeight == 0){
return max(leftHeight,rightHeight) + 1;
}//if
// 左右子树都有
else{
return min(leftHeight,rightHeight) + 1;
}
}
};
// 创建二叉树
TreeNode* CreateTreeByLevel(vector<int> num){
int len = num.size();
if(len == 0){
return NULL;
}//if
queue<TreeNode*> queue;
int index = 0;
// 创建根节点
TreeNode *root = new TreeNode(num[index++]);
// 入队列
queue.push(root);
TreeNode *p = NULL;
while(!queue.empty() && index < len){
// 出队列
p = queue.front();
queue.pop();
// 左节点
if(index < len && num[index] != -1){
// 如果不空创建一个节点
TreeNode *leftNode = new TreeNode(num[index]);
p->left = leftNode;
queue.push(leftNode);
}
index++;
// 右节点
if(index < len && num[index] != -1){
// 如果不空创建一个节点
TreeNode *rightNode = new TreeNode(num[index]);
p->right = rightNode;
queue.push(rightNode);
}
index++;
}//while
return root;
}
int main() {
Solution solution;
// -1代表NULL
vector<int> num = {4,5,-1,7};
TreeNode* root = CreateTreeByLevel(num);
cout<<solution.minDepth(root)<<endl;
}
分享到:
相关推荐
leetcode 数据结构题目中的答案,已经调试,直接运行,求二叉树的最小深度
* [Binary Search Tree](https://github.com/kamyu104/LeetCode#binary-search-tree) * [Breadth-First Search](https://github.com/kamyu104/LeetCode#breadth-first-search) * [Depth-First Search]...
leetcode下载 ARTS- ARTS打卡 Algorithm Leetcode -111 Minimum Depth of Binary Tree 本题的要求是给一个二叉树,返回这个二叉树的最小层级 Tips Tmux 基本操作: prefix := Ctrl+B session相关操作 查看/切换...
Tree(111) 二叉树的遍历包括: 前序遍历 中序遍历 后序遍历 层次遍历 Points: 采用中序遍历实现 若左右子树均不为空,返回深度更小的一个;若其中某一子树为空,返回另一子树的深度 每个节点(若不为空),则遍...
LeetCodeLeetCode solutions(Java)树Minimum Depth of Binary Tree栈evaluate-reverse-polish-notation穷举max-points-on-a-line链表sort-list排序insertion-sort-list树binary-tree-postorder-traversal树binary-...
binary-tree-postorder-traversal 树 binary-tree-preorder-traversal 链表 linked-list-cycle-ii 链表 linked-list-cycle 链表 copy-list-with-random-pointer 复杂度 single-number 动态规划 candy 贪心 gas-...
Minimum Depth of Binary Tree Maximum Depth of Binary Tree Path Sum Path Sum II Binary Tree Maximum Path Sum Populating Next Right Pointers in Each Node Sum Root to Leaf Numbers LCA of Binary Tree 线段...
1.1 树的最小深度Given a binary tree, find its minimum depth.The minimum depth is the n
最大公共字符串leetcode leetcode刷题打卡 接下来,坚持每周至少刷一道LeetCode题,刷题顺利按照牛客网LeetCode经典题目顺序进行,记录解题思路,与大家共享,同时也做个自我监督 第一周 1、树 题目: Given a ...
minimum_depth_binary_tree: twoSum: regularExpressionMathcing: sameTree: find_content_children: LeetCode 算法题 时间复杂度和空间复杂度权衡,时间复杂度的提升是以空间复杂度为代价的 仔细观察,LeetCode 上...