Leetcode 111. 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.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its minimum depth = 2.

DFS vs.BFS

这道题既可以通过DFS，也可以通过BFS求解。对于DFS而言，既以深度优先寻找叶子节点，随后依次自底向上更新到达叶子节点的距离，直到最后到达根节点。对于BFS而言，则是从根节点出发，自顶向下逐层遍历，直到找到包含叶子节点的层为止。

BFS和DFS都是树数据结构的常见解法，而且大部分情况下可以相互替换。我认为两者之间最大的不同是思考的出发点差异。一般DFS都是从叶子结点出发，采用逆推的方式向上更新；而BFS则是从根节点出发，顺序更细结果。

DFS 提交代码(>100%)

class Solution {

    private int findMinDepth(TreeNode node){
        if (node==null) return 0;
        int left  = findMinDepth(node.left);
        int right = findMinDepth(node.right);
        if (left==0&&right==0) {
            return 1;
        } else if (right==0){
            return left+1;
        } else if (left==0){
            return right+1;
        } else {
            return left<right?left+1:right+1;
        }
    }

    public int minDepth(TreeNode root) {
        return findMinDepth(root);
    }
}