104. Maximum Depth of Binary Tree

题目描述：

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.

题目翻译

给定一个二叉树，找到它的最大深度。

最大深度是沿着从根节点到最远叶节点的最长路径的节点的数量。

解题方案

标签： Depth-first Search

思路：

• 这是一道比较简单的树的题目，可以有递归和非递归的解法，递归思路简单，返回左子树或者右子树中大的深度加1，作为自己的深度即可。

• 非递归解法一般采用层序遍历(相当于图的BFS），因为如果使用其他遍历方式也需要同样的复杂度O(n). 层序遍历理解上直观一些，维护到最后的level便是树的深度。

Java代码：

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

Java代码：

public int maxDepth(TreeNode root) {  
    if(root == null)  
        return 0;  
    int level = 0;  
    LinkedList<TreeNode> queue = new LinkedList<TreeNode>();  
    queue.add(root);  
    int curNum = 1; //num of nodes left in current level  
    int nextNum = 0; //num of nodes in next level  
    while(!queue.isEmpty())  
    {  
        TreeNode n = queue.poll();  
        curNum--;  
        if(n.left!=null)  
        {  
            queue.add(n.left);  
            nextNum++;  
        }  
        if(n.right!=null)  
        {  
            queue.add(n.right);  
            nextNum++;  
        }  
        if(curNum == 0)  
        {  
            curNum = nextNum;  
            nextNum = 0;  
            level++;  
        }  
    }  
    return level;  
}

参考资料

• http://blog.csdn.net/linhuanmars/article/details/19659525
• 作者：Code_Ganker