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.

思路分析:这题和相似，可是如今要返回最小深度，递归的解法须要加一个特殊的推断。就是假设某个node比方root仅仅有一个孩子，这时不能返回最小深度是0。由于仅仅有在叶子节点处（而不是空处）才干计算深度，所以当左孩子为空，传入右孩子递归调用；当右孩子为空，传入左孩子递归调用。

而在没有这个问题，由于我们是求最大深度，某个node仅仅有一个孩子，我们会计深度为1而不是0。

递归解法例如以下。多加了对仅仅有一个孩子的情况的推断：

/** * Definition for binary tree * 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;        if(root.left == null) return minDepth(root.right) + 1;        if(root.right == null) return minDepth(root.left) + 1;        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;    }}

非递归解法借助队列进行BFS计算深度。当遇到第一个叶子节点返回深度就可以，最后加了一个return 0保证返回出口，事实上叶子节点必定存在。一定会从while循环里面就返回。

/** * Definition for binary tree * 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;        LinkedList
     
       treeNodeQueue = new LinkedList
      
       ();        int level = 1;        treeNodeQueue.add(root);        int curLevelNum = 1;        int nextLevelNum = 0;        while(!treeNodeQueue.isEmpty()){            TreeNode curNode = treeNodeQueue.poll();//find and remove; different from peek            if(curNode.left == null && curNode.right == null) return level;            curLevelNum--;            if(curNode.left != null){                treeNodeQueue.add(curNode.left);                nextLevelNum++;            }            if(curNode.right != null){                treeNodeQueue.add(curNode.right);                nextLevelNum++;            }            if(curLevelNum == 0){                level++;                curLevelNum = nextLevelNum;                nextLevelNum = 0;//added a level            }        }        return 0;    }}
      
     

版权声明：本文博客原创文章。博客，未经同意，不得转载。