leetcode-104：二叉树的最大深度

问题

给定一个二叉树，找出其最大深度
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数
说明: 叶子节点是指没有子节点的节点

示例：
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回它的最大深度 3

解法一：递归

后序遍历，因为要通过递归函数的返回值做计算树的高度
代码的逻辑是求根节点的高度，根节点的高度即为这棵树的最大深度

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

时间复杂度：，其中 n 为二叉树节点的个数。每个节点在递归中只被遍历一次
空间复杂度：，其中 height 表示二叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于二叉树的高度

解法二：广度优先搜索

package leetcode_104;
import javax.swing.tree.TreeNode;
import java.util.LinkedList;
import java.util.Queue;
public class solution {
    public int maxDepth(TreeNode root) {
        if (root == null){
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int depth = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++){
                TreeNode node = queue.poll();
                if (node.left != null){
                    queue.offer(node.left);
                }
                if (node.right != null){
                    queue.offer(node.right);
                }
            }
            depth += 1;
        }
        return depth;
    }
}

时间复杂度：，其中 n 为二叉树的节点个数，每个节点只会被访问一次
空间复杂度：此方法空间的消耗取决于队列存储的元素数量，其在最坏情况下会达到