大家好,我是宇哥
题目
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明:叶子节点是指没有子节点的节点。
输入:root=[3,9,20,null,null,15,7]输出:2
示例2
输入:root=[2,null,3,null,4,null,5,null,6]输出:5
提示:
树中节点数的范围在[0,]内
-=Node.val=
解题思路
深度优先:递归
叶子节点是,左右节点都为null的情况
当根节点为null的时候,返回0
当左或者右节点深度是0时,返回左+右+1
当左右节点深度都不为0时,返回左右节点中最小的长度+1
上代码:
publicintminDepth(TreeNoderoot){if(root==null)return0;//1当根节点为null的时候,返回0intleftCount=minDepth(root.left);//递归左节点intrightCount=minDepth(root.right);//递归右节点if(leftCount==0
rightCount==0)returnleftCount+rightCount+1;//2当左或者右节点有一个为深度是0时,返回左+右+1returnMath.min(leftCount,rightCount)+1;//3当左右节点都不为null时,返回左右节点中最小的长度+1}
广度优先-队列
使用广度优先搜索的方法,遍历整棵树。
当根节点为null的时候,返回0,节点不为null,加入队列中
第一层循环,循环节点层
第二层循环,循环每一层中的节点
当找到一个叶子节点时,直接返回这个叶子节点的深度。否则向队列中添加子节点
publicintminDepth(TreeNoderoot){if(root==null)return0;//如果节点为null返回0QueueTreeNodequeue=newLinkedList();queue.offer(root);//队列中放入根节点,intcount=1;//记录节点数while(!queue.isEmpty()){//循环每一层intsize=queue.size();//队列长度for(inti=0;isize;i++){//循环一层中的节点(1或2个)TreeNodenode=queue.poll();//从队列中取出节点if(node.left==nullnode.right==null){returncount;//遇见第一个叶子节点返回}if(node.left!=null){//左节点不null,放到队列中,说明不是叶子节点,queue.offer(node.left);}if(node.right!=null){//右节点不null,放到队列中,说明不是叶子节点,queue.offer(node.right);}}count++;//深度+1;}returncount;}
大佬们的解法
方法一:深度优先搜索
思路及解法
首先可以想到使用深度优先搜索的方法,遍历整棵树,记录最小深度。
对于每一个非叶子节点,我们只需要分别计算其左右子树的最小叶子节点深度。这样就将一个大问题转化为了小问题,可以递归地解决该问题。
代码
classSolution{publicintminDepth(TreeNoderoot){if(root==null){return0;}if(root.left==nullroot.right==null){return1;}intmin_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);}returnmin_depth+1;}}
复杂度分析
时间复杂度:O(N),其中N是树的节点数。对每个节点访问一次。
空间复杂度:O(H),其中H是树的高度。空间复杂度主要取决于递归时栈空间的开销,最坏情况下,树呈现链状,空间复杂度为O(N)。平均情况下树的高度与节点数的对数正相关,空间复杂度为O(logN)。
方法二:广度优先搜索
思路及解法
同样,我们可以想到使用广度优先搜索的方法,遍历整棵树。
当我们找到一个叶子节点时,直接返回这个叶子节点的深度。广度优先搜索的性质保证了最先搜索到的叶子节点的深度一定最小。
代码
classSolution{classQueueNode{TreeNodenode;intdepth;publicQueueNode(TreeNodenode,intdepth){this.node=node;this.depth=depth;}}publicintminDepth(TreeNoderoot){if(root==null){return0;}QueueQueueNodequeue=newLinkedListQueueNode();queue.offer(newQueueNode(root,1));while(!queue.isEmpty()){QueueNodenodeDepth=queue.poll();TreeNodenode=nodeDepth.node;intdepth=nodeDepth.depth;if(node.left==nullnode.right==null){returndepth;}if(node.left!=null){queue.offer(newQueueNode(node.left,depth+1));}if(node.right!=null){queue.offer(newQueueNode(node.right,depth+1));}}return0;}}
复杂度分析
时间复杂度:O(N),其中N是树的节点数。对每个节点访问一次。
空间复杂度:O(N),其中N是树的节点数。空间复杂度主要取决于队列的开销,队列中的元素个数不会超过树的节点数
欢迎广大人民群众,快乐三连击:
宇你同在HI