力扣 - 104. 二叉树的最大深度

题目

104. 二叉树的最大深度

思路1（递归）

• 自顶向下，利用递归
• 从子结构中择优，选择最大的那个
• 其实就是树的后序遍历

代码

class Solution {
    public int maxDepth(TreeNode root) {
        // 到底就开始返回
        if (root == null) {
            return 0;
        }

        // 获取左右子树的高度
        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);

        // 择优
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

复杂度分析

• 时间复杂度：\(O(N)\)，其中 N 为树的结点数量
• 空间复杂度：\(O(N)\)，其中 N 为树的最大高度

思路2（迭代）

• 使用迭代方法来做，利用队列实现
• 队列存储的是每一层的所有的结点数
• 同时还需要用一个res来存储层数
• 刚开始就要res初始化为0，同时将root根节点入队

代码

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int res = 0;
        
        while (!queue.isEmpty()) {
            // 获取上一层的元素个数
            int size = queue.size();
            // 将上一层元素出队同时将下一层元素入队
            while (size > 0) {
                TreeNode n = queue.poll();
                if (n.left != null) {
                    queue.offer(n.left);
                }
                if (n.right != null) {
                    queue.offer(n.right);
                }
                size--;
            }
            // 高度+1
            res++;
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：\(O(N)\)，其中 N 为树的结点个数
• 空间复杂度：\(O(N)\)，其中 N 为树的结点个数