题目

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

解题思路

这题很简单， 这里列出BFS和DFS得到解题方式，分别用队列和递归去计算其深度，BFS和之前的打印树二维数组很像可以看那里的解释，这里解释下DFS的递归函数，首先使用了取最大值得方法， 如果左边深度更深就用左边的， 反之用右边的， 相同则深度一致，代码如下。

Java代码实现

import java.util.*;

public class MaxDepth {
    public class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode(int x) { val = x; }
   }
    public int maxDepth(TreeNode root) {
        Queue<TreeNode> queue =  new LinkedList();
        if(root != null){
            queue.add(root);
        }else{
            return 0;
        }
        int depth = 0;
        while(!queue .isEmpty() ){
            Queue tmp = new LinkedList();
            for (TreeNode node : queue) {
                if(node.left != null){
                    tmp.add(node.left);
                }
                if(node.right != null){
                    tmp.add(node.right);
                }
            }
            queue = tmp;
            depth ++ ;
        }
        return depth;
    }
    public int maxDepthDFS(TreeNode root) {
        if(root == null){
            return 0;
        }
        return Math.max(maxDepthDFS(root.left), maxDepthDFS(root.right)) + 1;
    }
}