MaximumDepthOfBinaryTree [source code]

public class MaximumDepthOfBinaryTree {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

第一次做这个题目的时候的笔记:

这个刚开始想了半天硬是没有想出来，感觉还是学算法导论的时候学的太抽象了，具体的代码怎么写完全没有概念。
不过仔细看下来这个程序也是很简单的，就是一个很直接的recursion思维的应用：你所需要考虑的就是当前iteration怎样处理就行了：iteration for invariant（假设你拿到一个invariant from the lower level, what should you do in this iteration level so that overall the invariant is maintained).

无论是 tree 问题还是 DFS, 都是属于 recursion, 所以上来base case先处理好, 这个基本功不要忘记了;

问题本身还是很简单的, tree 的问题, 一个核心要理清的要务是: 你每一层的返回值代表的是什么. 这里要知道每一层的返回值代表的是max depth of subtree rooted at this node. 然后相应的在每一层应该怎么做 decision 就很一目了然了;

lc 上有纯手工写的 DFS 和 BFS itrative版本的代码: (这两个代码如果理解了, 非常有教育意义)
DFS:

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

    Stack<TreeNode> stack = new Stack<>();  
    Stack<Integer> value = new Stack<>();  
    stack.push(root);  
    value.push(1);  
    int max = 0;  
    while(!stack.isEmpty()) {  
        TreeNode node = stack.pop();  
        int temp = value.pop();  
        max = Math.max(temp, max);  
        if(node.left != null) {  
            stack.push(node.left);  
            value.push(temp+1);  
        }  
        if(node.right != null) {  
            stack.push(node.right);  
            value.push(temp+1);  
        }  
    }  
    return max;  
}  
// 7ms

这个代码看起来好像是 BFS, 其实是DFS, 只不过比较奇怪的地方是这个 DFS 是从右到左的探索过程. 把下面两个 if 的顺序换一下, 就是普通的 DFS 了; 事实上可以看到, 用 Stack 手工写 DFS 好像也不是一件很难的事情. 这个代码的意义在于, 目前看过的算法书里面, DFS 基本都是用recursion 来写, 也就是 Stack 干脆使用系统默认的 stack. 这个当然是很快的, 但是对于理解 DFS 的实质实现并不有利;

BFS:

public int maxDepth(TreeNode root) {  
    if(root == null) {  
        return 0;  
    }  
    Queue<TreeNode> queue = new LinkedList<>();  
    queue.offer(root);  
    int count = 0;  
    while(!queue.isEmpty()) {  
        int size = queue.size();  
        while(size-- > 0) {  
            TreeNode node = queue.poll();  
            if(node.left != null) {  
                queue.offer(node.left);  
            }  
            if(node.right != null) {  
                queue.offer(node.right);  
            }  
        }  
        count++;  
    }  
    return count;  
}  
// 3ms

这个算法相对来说比 DFS 复杂一些, 有两个 while 循环是因为第一个(outter) 循环处理的是不同的depth(因为 BFS 是iterate by depth); 而inner loop处理的是within one depth以内的处理;这个跟之前看书的时候碰到的 BFS 还是有点差别的, 那里当时就只有一个 loop.
为什么会有这个区别呢? 如果你的目的只是完成 BFS 本身, 其实一个 loop 是足够的, 因为这个 queue就能保证search by depth. 但是我们这里要完成的不仅仅是一个 traversal, 而是要完成一个count 1 per depth的过程; 如果不在outter loop的内部用另外一个 loop 区分开每一个 depth 的处理, 就没有办法知道什么时候应该increment counter;

另外这里还有一个遗留问题: 你肯定很想把这个算法改成tail recursion, 毕竟这个算法很简单, 不过这里好像是没有办法改成tail recursion的, 因为这个 max 的操作你是无论如何都避免不了的: 必然要发生在上行返回之后.

Problem Description

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Subscribe to see which companies asked this question.

Hide Tags Tree Depth-first Search
Hide Similar Problems (E) Balanced Binary Tree (E) Minimum Depth of Binary Tree