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.
问题：找最小深度
思想：104题是找最大深度
（1）递归：根节点的左孩子为空时返回右子树的最小深度+1，当右孩子为空时返回左子树的最小深度+1，当左右孩子均存在时返回左右子树最小深度值+1
（2）队列：借助队列，类似于按照层次查找，出队得到节点node，如果node没有左右孩子则返回深度值，如果它有孩子将其孩子加入队列
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public int minDepth(TreeNode root){ if(root==null) return 0; int dep=1; Queue<TreeNode> q=new LinkedList(); q.add(root); while(!q.isEmpty()){ int size=q.size(); for(int i=0;i<size;i++){ TreeNode node=q.poll(); if(node.left==null &&node.right==null) return dep; if(node.left!=null) q.add(node.left); if(node.right!=null) q.add(node.right); } dep++; } return dep; } } public int minDepth(TreeNode root) { if(root==null) return 0; if(root.left==null&&root.right==null)return 1; if(root.left==null) return minDepth(root.right)+1; if(root.right==null) return minDepth(root.left)+1; return Math.min(minDepth(root.right)+1, minDepth(root.left)+1); }
