前言:
现在看官们对“二叉树深度计算公式”大概比较讲究,姐妹们都需要知道一些“二叉树深度计算公式”的相关文章。那么小编同时在网摘上汇集了一些关于“二叉树深度计算公式””的相关文章,希望朋友们能喜欢,各位老铁们快快来学习一下吧!题目描述
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明:叶子节点是指没有子节点的节点。
示例
输入:
3 / \9 20 / \ 15 7
输出:
2写在前面
本文答案参考自 LeetCode 官方题解。[敲打]
解法1:深度优先搜索
没什么好说的吧[机智][看]
代码
class Solution { public int minDepth(TreeNode root) { if (root == null) { return 0; } if (root.left == null && root.right == null) { return 1; } int min_depth = Integer.MAX_VALUE; if (root.left != null) { min_depth = Math.min(minDepth(root.left), min_depth); } if (root.right != null) { min_depth = Math.min(minDepth(root.right), min_depth); } return min_depth + 1; }}作者:LeetCode-Solution链接:来源:力扣(LeetCode)解法2:广度优先搜索
一层一层地往下找,找到的第一个叶子节点当然就是 距离根节点最近的叶子节点 啦~[耶]
代码
class Solution { class QueueNode { TreeNode node; int depth; public QueueNode(TreeNode node, int depth) { this.node = node; this.depth = depth; } } public int minDepth(TreeNode root) { if (root == null) { return 0; } Queue<QueueNode> queue = new LinkedList<QueueNode>(); queue.offer(new QueueNode(root, 1)); while (!queue.isEmpty()) { QueueNode nodeDepth = queue.poll(); TreeNode node = nodeDepth.node; int depth = nodeDepth.depth; if (node.left == null && node.right == null) { return depth; } if (node.left != null) { queue.offer(new QueueNode(node.left, depth + 1)); } if (node.right != null) { queue.offer(new QueueNode(node.right, depth + 1)); } } return 0; }}作者:LeetCode-Solution链接:来源:力扣(LeetCode)
版权声明:
本站文章均来自互联网搜集,如有侵犯您的权益,请联系我们删除,谢谢。