MinimumDepthOfBinaryTree [source code]

public class MinimumDepthOfBinaryTree {
static
/******************************************************************************/
public class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        return 1 + Math.min((left == 0 ? right : left), (right == 0 ? left : right));
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        MinimumDepthOfBinaryTree.Solution tester = new MinimumDepthOfBinaryTree.Solution();
        TreeNode t1 = new TreeNode(0);
        TreeNode t2 = new TreeNode(0);
        System.out.println(t1.equals(t2)); //false
    }
}

这个问题总体来说还是非常简单的, 反正不要想的太复杂, 直接从 recursion 的角度来思考就行了. 当然也可以从 DFS 的角度来思考, 不过如果用 accum 的思路来做(寻找每一个root-to-leaf的 path), 那么记得退出每一个 subtree 的时候要 undo changes;

最后的速度是1(16), 可能也是题目比较老的关系了;

另外这个题目还体现了另外一个问题:
注意我这里左右的结果返回回来了其实还加了一个处理, 就是如果是0, 就丢弃, 不参与 min 的计算; 这个是分析问题本身的逻辑得到的. 当然这个题目还可以用另外一种思路, 就是 base case 不判断 Null, 而是判断leaf or half-leaf, 这个也可以. 反正用 recursion 问题做 tree 的时候, 时不时是要思考一下你的 base case 到底用哪种方案. 一般来说应该是两种方案都可以做出来, 不过可能某一种方案相对会简单一些;

这个是类似我的思路, 但是另外一种写法:

public class Solution {  
    public int minDepth(TreeNode root) {  
        if(root==null) return 0;  
        int left = minDepth(root.left);  
        int right= minDepth(root.right);  
        if(left == 0 || right == 0)  
            return left + right +1;  
        else  
            return Math.min(left,right) + 1;  

    }  
}

discussion里面认为, 这个题目其实用 BFS 更好, 因为我们要找的是最近的一个 leaf, 所以如果一个 leaf很近, 那么碰到它之后我们就可以立刻停止, 而不用像 DFS 那样必须走完整个 tree;

这个问题按照 BFS 来走,严格来说连一个search problem都不算了, 就是直接一个 stream 一样的算法, 走到一个条件就停止就行了;

public int minDepth(TreeNode root) {  
    if(root==null) return 0;  

    Queue<TreeNode> queue = new LinkedList<TreeNode>();  
    queue.add(root);  
    TreeNode endOfLevel = root;  
    int depth = 1;  

    while( !queue.isEmpty() ) {  
        TreeNode node = queue.remove();  
        if(node.left==null && node.right==null) return depth;  
        if(node.left!=null) queue.add(node.left);  
        if(node.right!=null)  queue.add(node.right);  
        if(node == endOfLevel) {  
            endOfLevel = node.right==null ? node.left : node.right;  
            depth++;  
        }  
    }  

    return depth;  
}

这个代码很聪明, 而且很容易读懂, 而且跟平常的我们写 BFS 的方法不太一样. 平时我们写 BFS 都是一个 iteration 做一个 level, 在这个 iteration 内部存住当前 level 的 size 之后, 一个 inner loop 来处理这个 level 就行了; 这个人的做法不一样, 这个人的这个写法就是一个 iteration 处理一个 node. 他处理 level 的方式是用一个end of level的指针来划分不同的 level, 这个想法还是挺聪明的; 这种 BFS 的思路其实是可以推广到其他需要 BFS 的问题的;

这个是另一个 BFS 的版本:

public class Solution {  
    public int minDepth(TreeNode root) {  
        if (root == null)  
            return 0;  
        int depth = 1;  
        Queue<TreeNode> queue = new LinkedList<TreeNode>();  
        TreeNode temp,magic = new TreeNode(0);  
        queue.add(root);  
        queue.add(magic);  
        while(!queue.isEmpty()){  
            temp = queue.poll();  
            if(temp.equals(magic)){  
                if(!queue.isEmpty()){  
                    depth++;  
                    queue.add(magic);  
                }  
                continue;  
            }  
            if(temp.left == null && temp.right == null)  
                return depth;  
            if(temp.left != null)  
                queue.add(temp.left);  
            if(temp.right != null)  
                queue.add(temp.right);  
        }  
        return depth;  
    }  
}

其实思路是一样的, 感觉这些2014年的时候写的 BFS 都喜欢这样来处理 level(现在的做法是预存当前 level 的 size 来控制内循环的次数). 他这里的做法是, 用dummy node来做分界线, 这个 dummy 是要直接进入 queue 参与运算的, 感觉不如上面那个好, 而且上面那种直接变量比较的也更好理解一些;
需要注意的是, 如果这里的 root 的 val 是0, 那么root.equals(magic)是不会通过的! 因为虽然 val 相等, 但是并不是一个 object(.equals 判断的是 dereference 之后的内容是否 identical). 这个文件的 main 函数里面我试了,确实是 false;

public int minDepth(TreeNode root) {  
    if (root == null){  
        return 0;  
    }  
    Queue<TreeNode> queue = new LinkedList<TreeNode>();  
    queue.add(root);  
    int depth = 1;  
    while (!queue.isEmpty()){  
        int size = queue.size(); // determine the loop size  
        for (int i = 0; i< size; i++){  
            TreeNode node = queue.poll();  
            if (node.left == null && node.right == null){  
                return depth;  
            }  
            if (node.left!=null){  
                queue.add(node.left);  
            }  
            if (node.right!=null){  
                queue.add(node.right);  
            }  
        }  
        depth ++;  
    }  
    return depth;  
}

这个就是传统方式的 DFS 了, 代码也是很清晰;

其他的基本都差不多了. 这些老题目的帖子里还真是经常看到惊喜;

Problem Description

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.

Difficulty:Easy
Total Accepted:169.3K
Total Submissions:513.5K
Contributor: LeetCode
Related Topics
tree depth-first search breadth-first search
Similar Questions
Binary Tree Level Order Traversal Maximum Depth of Binary Tree