[LeetCode] 111. Minimum Depth of Binary Tree ☆(二叉树的最小深度)
2023-09-14 09:07:35 时间
[Leetcode] Maximum and Minimum Depth of Binary Tree 二叉树的最小最大深度 (最小有3种解法)
描述
解析
递归深度优先搜索
当求最大深度时,我们只要在左右子树中取较大的就行了。
然而最小深度时,如果左右子树中有一个为空会返回0,这时我们是不能算做有效深度的。
所以分成了三种情况,左子树为空,右子树为空,左右子树都不为空。当然,如果左右子树都为空的话,就会返回1。
广度优先搜索(类似层序遍历的思想)
递归解法本质是深度优先搜索,但因为我们是求最小深度,并不一定要遍历完全部节点。如果我们用广度优先搜索,是可以在遇到第一个叶子节点时就终止并返回当前深度的。
代码
递归深度优先搜索
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int minDepth(TreeNode root) { if(root == null){ return 0; } int depth = 0; if(root.left != null && root.right != null){ int left = minDepth(root.left); int right = minDepth(root.right); depth = Math.min(left, right); } else if (root.left != null){ depth = minDepth(root.left); } else if (root.right != null){ depth = minDepth(root.right); } return depth + 1; } }
广度优先搜索(类似层序遍历的思想)
public class Solution { public int minDepth(TreeNode root) { Queue<TreeNode> queue = new LinkedList<TreeNode>(); if(root!=null) queue.offer(root); int depth = 0; while(!queue.isEmpty()){ int size = queue.size(); depth++; for(int i = 0; i < size; i++){ TreeNode curr = queue.poll(); if(curr.left == null && curr.right == null){ return depth; } if(curr.left != null) queue.offer(curr.left); if(curr.right != null) queue.offer(curr.right); } } return depth; } }
相关文章
- Java实现 LeetCode 671 二叉树中第二小的节点(遍历树)
- Java实现 LeetCode 559 N叉树的最大深度(遍历树,其实和便利二叉树一样,代码简短(●ˇ∀ˇ●))...
- Java实现 LeetCode 559 N叉树的最大深度(遍历树,其实和便利二叉树一样,代码简短(●ˇ∀ˇ●))...
- Java实现 LeetCode 110 平衡二叉树
- Java实现 LeetCode 104 二叉树的最大深度
- Java实现 LeetCode 103 二叉树的锯齿形层次遍历
- Java实现 LeetCode 102 二叉树的层次遍历
- Java实现 LeetCode 13 罗马数字转整数
- 【哈希表】leetcode 128. 最长连续序列【中等】
- LeetCode(124):二叉树中的最大路径和
- LeetCode(104):二叉树的最大深度
- LeetCode(53):最大子序和
- 每日一道 LeetCode (27):二叉树的最小深度
- 每日一道 LeetCode (22):二叉树的最大深度
- [LeetCode] Top K Frequent Elements
- LeetCode-998. 最大二叉树 II【最大二叉树】
- leetcode 106. 从中序与后序遍历序列构造二叉树
- [LeetCode] 543. 二叉树的直径 ☆(递归、数最大深度)
- leetcode - Combination Sum
- leetcode 504. Base 7
- 【Leetcode刷题Python】110. 平衡二叉树
- 【Leetcode刷题Python】111. 二叉树的最小深度
- 【Leetcode刷题Python】297. 二叉树的序列化与反序列化
- 【LeetCode】103. 二叉树的锯齿形层序遍历