leetcode104 -- 二叉树的最大深度Java

leetcode104 -- 二叉树的最大深度Java

题目描述：

方法一：深度优先遍历

• 一般对于树的题目，我们都是可以用到递归的思想
• 如果我们知道了左子树和右子树的最大深度l和r，那么该二叉树的最大深度为 max(l, r) + 1
• 左右子树的最大深度又可以用同样的方式来进行计算

代码实现：

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null){
            return 0;
        }
        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);
        // 最后的结果为左右子树中更高的 + 1即可
        return 1 + Math.max(leftHeight, rightHeight);
    }
}     

复杂度分析：

方法二：广度优先搜索

• 每次扩展下一层的时候，不同于广度优先搜索的每次只从队列中拿出一个节点，我们需要拿出队列中的所有节点进行扩展
• 这样可以保证每次扩展完的时候队列里存放的就是当前层的所有节点，即一层一层的进行扩展，最后我们用一个变量ans来维护扩展次数

class Solution {
    public int maxDepth(TreeNode root) {
    	if (root == null){
            return 0;
        }
        // 创建一个队列来存取每一层的节点
        Queue queue = new linkedList();
        queue.offer(root);
        // 设置一个变量来记录层数
        int ans = 0;
        while (!queue.isEmpty()){
            int size = queue.size();
            while (size > 0){
                // 每次将队列中的元素d一个出去
                TreeNode node = queue.poll();
                if (node.left != null){
                    queue.offer(node.left);
                }
                if (node.right != null){
                    queue.offer(node.right);
                }
                size--;
            }
            ans++;
        }
        // 当一棵树里面所有节点都扫过一遍，一层一层扩展就结束了，直接返回层数即可，就是高度
        return ans;
    }
}

复杂度分析：