LeetCode--111. Minimum Depth of Binary Tree

本文主要是介绍LeetCode--111. Minimum Depth of Binary Tree，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接:https://leetcode.com/problems/minimum-depth-of-binary-tree/

求树的最小深度，也就是说:沿着树的路径从根节点到最近叶节点的距离。

需要一个队列进行层次遍历（BFS,对层次进行计数），在某一层找到叶节点时返回。

class Solution {public static int minDepth(TreeNode root) {if(root==null)return 0;Queue<TreeNode> q=new LinkedList<TreeNode>();q.add(root);int count=0;while(!q.isEmpty()){count++;int len=q.size();for(int i=0;i<len;i++){TreeNode node=q.poll();if(node.left!=null)q.add(node.left);if(node.right!=null)q.add(node.right);if(node.left==null && node.right==null)return count;}}return count;}
}

另外一种BFS解法空间复杂度比上面的大一点，但是比后面的DFS具体运行时间少一点（不用遍历所有树节点）：

import javafx.util.Pair;
class Solution {public int minDepth(TreeNode root) {Queue<Pair<TreeNode,Integer>> records=new LinkedList<Pair<TreeNode,Integer>>();if(root==null)return 0;records.add(new Pair(root,1));int min=1;while(!records.isEmpty()){Pair<TreeNode,Integer> temp=records.poll();TreeNode currentNode=temp.getKey();int depth=temp.getValue();min=depth;if(currentNode.left==null && currentNode.right==null)break;if(currentNode.left!=null)records.add(new Pair(currentNode.left,depth+1));if(currentNode.right!=null)records.add(new Pair(currentNode.right,depth+1));}return min;}
}

再来看看递归解法，递归解法与树的最大深度解法类似（https://blog.csdn.net/To_be_to_thought/article/details/84555289）：

class Solution {public int minDepth(TreeNode root) {if(root==null)return 0;if(root.left==null && root.right==null)return 1;int min=Integer.MAX_VALUE;if(root.left!=null)min=Math.min(min,minDepth(root.left));if(root.right!=null)min=Math.min(min,minDepth(root.right));return min+1;}
}

基于栈的深度优先搜索：

import javafx.util.Pair;
class Solution {public int minDepth(TreeNode root) {Stack<Pair<TreeNode,Integer>> records=new Stack<Pair<TreeNode,Integer>>();if(root==null)return 0;records.add(new Pair(root,1));int min=Integer.MAX_VALUE;while(!records.isEmpty()){Pair<TreeNode,Integer> temp=records.pop();TreeNode currentNode=temp.getKey();int depth=temp.getValue();if(currentNode.left==null && currentNode.right==null)min=Math.min(min,depth);;if(currentNode.left!=null)records.add(new Pair(currentNode.left,depth+1));if(currentNode.right!=null)records.add(new Pair(currentNode.right,depth+1));}return min;}
}

 

 

这篇关于LeetCode--111. Minimum Depth of Binary Tree的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---