Given a binary tree, find its mi

• 层次遍历法

public class MinimumDepthOfBinaryTree {
    static boolean isLeaf(TreeNode root){
        if(root.left == null && root.right == null){
            return true;
        }
        return false;
    }   
    public static int run(TreeNode root) {  
        if(root != null){
            TreeNode temRoot;
            int count = 0;
            Queue<TreeNode> queue = new LinkedList<>(); 
            queue.add(root);
            root.val = 1;
            while(queue.size() != 0){
                temRoot = queue.poll();
                int layer = temRoot.val;
                if(isLeaf(temRoot)){
                    return layer;
                }
                if(temRoot.left != null){
                    queue.add(temRoot.left);
                    temRoot.left.val = temRoot.val + 1;
                }
                if(temRoot.right != null){
                    queue.add(temRoot.right);
                    temRoot.right.val = temRoot.val + 1;
                }
            }
        }
      return 0;
    }
    private static void build(TreeNode root) {
        // TODO Auto-generated method stub
        setLeft(root);
        setRight(root);
        setLeft(root.left);
        setLeft(root.right);
    }
    public static void setLeft(TreeNode root){
        root.left = new TreeNode(0);
    }
    public static void setRight(TreeNode root){
        root.right = new TreeNode(0);
    }
    //运用层次遍历计算
    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(0);
        build(treeNode);
        System.out.println(run(treeNode));;
    }

• 用层次遍历方法很简单，但是用深度遍历法则需要好好思考思考，递归就是整体考虑，就把run当做了求最小值的方法

class Solution {
public:
    int run(TreeNode *root) 
    {
        if(root == nullptr) return 0;
        if(root->left == nullptr) // 若左子树为空，则返回右子树的最小深度+1
        {
            return run(root->right)+1;
        }
        if(root->right == nullptr) // 若右子树为空，则返回左子树的最小深度+1
        {
            return run(root->left)+1;
        }
        // 左右子树都不为空时，取较小值
        int leftDepth = run(root->left);
        int rightDepth = run(root->right);
        return (leftDepth<rightDepth)?(leftDepth+1):(rightDepth+1);
    }
};