#LeetCode# 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.

自从来法国接触了OCaml，对递归从本能地抵触到现在本能地依赖...以前抵触是因为在国内刚讲C语言，老师就说递归不好效率低一般我们要避免使用，然后一个学期的OCaml课老师对于递归的洗脑，让我也变成了又懒又笨的依赖递归的人了。废话不多说，上代码。

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

public class Solution {

    public int maxDepth(TreeNode root) {

        if (root == null)

            return 0;

        return Math.max(maxDepth (root.left), maxDepth (root.right)) + 1 ;

    }

}

直接手写代码，不过三次才Accepted，说说遇到的问题吧。

1.顾着高兴，直接return  (maxDepth (root.left), maxDepth (root.right)) + 1

2.root==null，刚开始二逼写成val=null...

3.第一次用Java的max，以为也是max(int, int)，谁知是Math.max(int, int)

一会儿吃完长棍，有心情了再写非递归的吧

LOL

再来完成下非递归的代码。

先说下思路，递归我们考虑的是DFS-深度优先，不使用递归的话，可以考虑BFS-广度优先。即层序遍历，遍历到最后一层（叶子）就是树的深度，这个时候再选择最大值即可。


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; //当前层剩余的节点数目
    int nextNum = 0; //下一层的节点数目
    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;

}

这个不是太好理解，再来一个好理解的版本。

public class Solution {

    public int maxDepth(TreeNode root) {

        if(root == null)    return 0;

         

        // Non-recursive, use level order triversal

        ArrayList<TreeNode> q = new ArrayList<TreeNode>();

        q.add(root);

        int depth = 0;

         

        while(!q.isEmpty()) {

            ArrayList<TreeNode> next = new ArrayList<TreeNode>();

            for(TreeNode node : q) {

                if(node.left != null)   next.add(node.left);

                if(node.right != null)  next.add(node.right);

            }

            q = new ArrayList<TreeNode>(next);

            depth++;

        }

         

        return depth;

    }

}