【LeetCode】Minimum Depth of Binary Tree
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
递归和非递归，此提比较简单。广度优先遍历即可。关键之处就在于如何保持访问深度。
下面是4种代码：
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue; class TreeNode {
int val;
TreeNode left;
TreeNode right; TreeNode(int x) {
val = x;
}
}
public class MinimumDepthofBinaryTree {
/**
* 递归深度遍历
* @param root
* @return
*/
public int minDepth1(TreeNode root) {
if(root==null)
return 0;
if(root.left==null&&root.right==null){
return 1;
}
int left=minDepth1(root.left);
int right=minDepth1(root.right);
if(left==0){
return right+1;
}
if(right==0){
return left+1;
}
else{
return Math.min(right, left)+1;
}
}
public int minDepth2(TreeNode root) {
if(root==null)
return 0;
int left=minDepth1(root.left);
int right=minDepth1(root.right); if(left==0&&right==0){
return 1;
}
if(left==0){
right= Integer.MAX_VALUE;
}
if(right==0){
left=Integer.MAX_VALUE;
} return Math.min(right, left)+1; } /**
* 广度优先搜索。一旦发现叶子结点，返回遍历深度。
* @param root
* @return
*/
public int minDepth3(TreeNode root) {
if(root==null){
return 0;
}
Queue<TreeNode>queue=new LinkedList<>();
queue.add(root);
int count=queue.size();//用来保存访问当前层次剩余未访问的节点。
int depth=1;//用来保存二叉树的访问深度
while(!queue.isEmpty()){
//广度遍历
TreeNode topNode=queue.poll();
count--;
if(topNode.left!=null){
queue.add(topNode.left);
}
if(topNode.right!=null){
queue.add(topNode.right);
}
//发现叶子节点
if(topNode.left==null&&topNode.right==null){
return depth;
}
//访问一层完毕
if(count==0){
depth++;
count=queue.size();
} }
return 0;
}
/**
* 广度优先搜索。一旦发现叶子结点，返回遍历深度。
* @param root
* @return
*/
public int minDepth4(TreeNode root) {
if(root==null){
return 0;
}
List<TreeNode>list=new ArrayList<>();
int count=1;
list.add(root);
while(list.size()!=0){
List<TreeNode>singleList=new ArrayList<>();
for(TreeNode t:list){
if(t.left!=null){
singleList.add(t.left);
}if(t.right!=null){
singleList.add(t.right);
}
if(t.left==null&&t.right==null){
return count;
}
}
count++;
list=singleList;
}
return 0;
}
public static void main(String[] args) {
TreeNode rootNode1 = new TreeNode(1);
TreeNode rootNode2 = new TreeNode(2);
TreeNode rootNode3 = new TreeNode(3);
TreeNode rootNode4 = new TreeNode(4);
TreeNode rootNode5 = new TreeNode(5);
TreeNode rootNode6 = new TreeNode(6);
TreeNode rootNode7 = new TreeNode(7);
rootNode1.left = rootNode2;
rootNode1.right = rootNode3;
rootNode2.left = rootNode4;
rootNode2.right = rootNode5;
rootNode3.left = rootNode6;
rootNode3.right = rootNode7;
MinimumDepthofBinaryTree minimumDepthofBinaryTree=new MinimumDepthofBinaryTree();
System.out.println(minimumDepthofBinaryTree.minDepth4(rootNode1)); } }