Question :
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.
Anwser 1 :
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int minDepth(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (root == NULL) return 0;
int left = minDepth(root->left) + 1;
int right = minDepth(root->right) + 1;
// leaf
if (left == 1 || right == 1)
return left > right ? left : right;
return left < right ? left : right;
}
};
Anwser 2 :
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int minDepth(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (root == NULL) return 0;
int depth = 1;
queue <TreeNode *> current;
queue <TreeNode *> next;
current.push(root);
while (!current.empty())
{
while (!current.empty())
{
TreeNode *n = current.front();
current.pop();
if (n->left==NULL && n->right == NULL) return depth;
if (n->left) next.push(n->left);
if (n->right) next.push(n->right);
}
queue <TreeNode *> t; // init queue
current = next;
next = t;
depth += 1;
}
return depth;
}
};
分享到:
相关推荐
leetcode 数据结构题目中的答案,已经调试,直接运行,求二叉树的最小深度
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-...
* [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]...
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 线段...
Minimum Depth of Binary Tree 本题的要求是给一个二叉树,返回这个二叉树的最小层级 Tips Tmux 基本操作: prefix := Ctrl+B session相关操作 查看/切换session prefix s 离开Session prefix d 重命名当前Session ...
1.1 树的最小深度Given a binary tree, find its minimum depth.The minimum depth is the n
Minimum Depth of Binary Tree(111) 二叉树的遍历包括: 前序遍历 中序遍历 后序遍历 层次遍历 Points: 采用中序遍历实现 若左右子树均不为空,返回深度更小的一个;若其中某一子树为空,返回另一子树的深度 每个...
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. 解题思路: 思路一:深度优先遍历,递归遍历左右子树...
minimum_depth_binary_tree: twoSum: regularExpressionMathcing: sameTree: find_content_children: LeetCode 算法题 时间复杂度和空间复杂度权衡,时间复杂度的提升是以空间复杂度为代价的 仔细观察,LeetCode 上...