问题描述:
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.
原问题链接:https://leetcode.com/problems/minimum-depth-of-binary-tree/
问题分析
粗看起来,这个问题比较简单,因为要求的是二叉树的最短长度,那么只要找到它到叶节点的最近的距离就可以了。而这里可以很容易的得到一个递归的关系,就是minDepth(root) = Math.min(minDepth(root.left), minDepth(root.right)) + 1;
于是我们可以得到如下的代码:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public int minDepth(TreeNode root) { if(root == null) return 0; return Math.min(minDepth(root.left), minDepth(root.right)) + 1; } }
在实际运行的时候却提示结果错误了。这里还有一个额外的要求,就是因为要找一个到叶节点的最近距离。在一些特殊的情况下,比如根节点的某个子树为空或者两个子树都是空,那么我们要啊返回的结果就不一样。我们必须要尽量找到那个有叶子节点的一边,而不是纯找最短的路径。把这两个条件考虑在内之后。
于是我们可以得到如下的代码:
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public int minDepth(TreeNode root) { if(root == null) return 0; int a = minDepth(root.left); int b = minDepth(root.right); if(a + b == 0) return 1; if(a * b == 0) return a + b + 1; return Math.min(a, b) + 1; } }
相关推荐
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-...
最大公共字符串leetcode leetcode刷题打卡 接下来,坚持每周至少刷一道LeetCode题,刷题顺利按照牛客网LeetCode经典题目顺序进行,记录解题思路,与大家共享,同时也做个自我监督 第一周 1、树 题目: Given a ...
LeetCode判断字符串是否循环 leetcode Coding with Lin on 1. Minimum Depth of Binary Tree(111) 二叉树的遍历包括: 前序遍历 中序遍历 后序遍历 层次遍历 Points: 采用中序遍历实现 若左右子树均不为空,返回...
leetcode 数据结构题目中的答案,已经调试,直接运行,求二叉树的最小深度
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]...
leetcode下载 ARTS- ARTS打卡 Algorithm Leetcode -111 Minimum Depth of Binary Tree 本题的要求是给一个二叉树,返回这个二叉树的最小层级 Tips Tmux 基本操作: prefix := Ctrl+B session相关操作 查看/切换...
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_binary_tree: twoSum: regularExpressionMathcing: sameTree: find_content_children: LeetCode 算法题 时间复杂度和空间复杂度权衡,时间复杂度的提升是以空间复杂度为代价的 仔细观察,LeetCode 上...
1.1 树的最小深度Given a binary tree, find its minimum depth.The minimum depth is the n