135 二叉树的最小深度

问题描述：给定一个二叉树，找出其最小深度，最小深度是从根节点到最近叶子节点的路径上的节点数量，说明叶子节点是指没有子节点的节点。

DFS求解：通过全局变量记录最小的深度，并对于深度大于最小深度的进行剪枝。

int minDepth=Integer.MAX_VALUE;
public void dfs(TreeNode root,int level)
{
if(level>=minDepth)
{
return;
???????}
if(root.left==null&&root.right==null)
{
if(level>=minDepth){return;}
minDepth=level;
}
if(root.left!=null)
{
dfs(root.left,level+1);
}
if(root.right!=null)
{
dfs(root.right,level+1);
}

}
public int max(TreeNode root)
{
dfs(root,1);
return minDepth;
}

BFS求解：只要遇到一个节点，左节点和右节点均为null的时候直接返回，

public int minLevel(TreeNode root)
{
Queue<Integer>queue=new LinkedList<>();
queue.add(root);
int level=0;
while(!queue.isEmpty())
{
level++;
int queueSize=queue.size();
for(int i=0;i<queueSize;i++)
{
TreeNode tempNode=queue.poll();
if(tempNode.left==null&&tempNode.right==null)
{
return level;
}
if(tempNode.left!=null){queue.add(tempNode.left);}
if(tempNode.right!=null){queue.add(tempNode.right);}
}
}
}