55(1)-二叉树的深度

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

树的结构本身就是一种递归的结构，所以很适合使用递归的解法来解决。

树中一个结点的深度就是其（左子树和右子树的最大深度）+ 1，递归代码如下:

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

递归其实实际是利用的栈实现的，只不过利用的调用栈，我们也可以使用一个队列来代替这个自动调用。

public int depth2(TreeNode node) {
        Queue<TreeNode> queue = new LinkedList<>();
        int depth = 0;
        queue.add(node);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode childNode = queue.remove();
                if(childNode.left != null){
                    queue.add(childNode.left);
                }
                if(childNode.right != null){
                    queue.add(childNode.right);
                }
            }
            depth++;
        }
        return depth;
}

主要思路就是按照层去遍历树，树的深度就等于层数。