网站开发网络,建立门户网站的意义,广州重点场所,微信官网网页版目录
题目描述#xff1a;
#xff08;递归#xff09;代码#xff1a; #xff08;非递归、层次遍历#xff09;代码#xff1a; 题目描述#xff1a;
给定一个二叉树#xff0c;找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说…目录
题目描述
递归代码 非递归、层次遍历代码 题目描述
给定一个二叉树找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明叶子节点是指没有子节点的节点。
示例 1 输入root [3,9,20,null,null,15,7]
输出2示例 2
输入root [2,null,3,null,4,null,5,null,6]
输出5
提示
树中节点数的范围在 [0, 10^5] 内-1000 Node.val 1000
递归代码
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public int minDepth(TreeNode root) {if(rootnull){return 0;}int rightminDepth(root.right);int leftminDepth(root.left);if(right0){return left1;}if(left0){return right1;}return Math.min(left,right)1;}
} 非递归、层次遍历代码 用层次遍历实现
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public int minDepth(TreeNode root) {if(rootnull){return 0;}QueueTreeNode queuenew LinkedList();queue.add(root);int count0;while (!queue.isEmpty()){int sizequeue.size();count;for(int i0;isize;i){TreeNode peek queue.remove();if(peek.rightnull peek.leftnull){return count;}if (peek.right!null) {queue.add(peek.right);}if(peek.left!null){queue.add(peek.left);}}}return count;}
}
