LeetCode 104题代码超时求助：二叉树最大深度解法优化

Hey there! Let's dig into why your first approach is hitting a Time Limit Exceeded (TLE) error, and walk through straightforward fixes to get it running efficiently.

The Root Cause of the Timeout #

Your initial code has a critical inefficiency: it recalculates the depth of left and right subtrees multiple times in the ternary operator. Let's break down the line causing the issue:

return (maxDepth(root.left)+1) > (maxDepth(root.right)+1)? (maxDepth(root.left)+1):(maxDepth(root.right)+1);

Here's what happens:

1. First, you compute maxDepth(root.left)+1 once to compare it with maxDepth(root.right)+1
2. Then, if the left depth is larger, you compute maxDepth(root.left)+1 again to return it
3. Same for the right side—if it's larger, you run maxDepth(root.right)+1 a second time

This leads to exponential time complexity (O(2^n) in the worst case, like a skewed tree). Every node gets visited multiple times instead of just once, which blows up the runtime for larger trees and triggers the TLE.

Simple Optimization: Cache Subtree Depths #

The fix is straightforward: calculate the left and right subtree depths once each, store them in variables, then use those values to compute the max depth. This reduces the time complexity to O(n) (each node is visited exactly once), which is efficient enough for LeetCode's test cases.

Here's the optimized recursive code:

public int maxDepth(TreeNode root) { 
    if(root == null ) { 
        return 0 ; 
    } 
    // Calculate depths once and reuse them
    int leftDepth = maxDepth(root.left);
    int rightDepth = maxDepth(root.right);
    // Return the larger depth plus 1 (for the current node)
    return Math.max(leftDepth, rightDepth) + 1;
}

Alternative: Iterative Approaches (Avoid Recursion Stack Overflow) #

If you're dealing with extremely deep trees, recursive solutions can hit a StackOverflowError (since Java's recursion stack has a limit). For those cases, iterative methods using BFS (level-order traversal) or DFS are better options:

BFS (Level-Order Traversal) #

This counts each level of the tree as one depth increment:

import java.util.LinkedList;
import java.util.Queue;

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    int depth = 0;
    
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        depth++;
        // Process all nodes in the current level
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
    }
    return depth;
}

Iterative DFS #

This mimics the recursive approach using a stack to track nodes and their current depth:

import java.util.Stack;
import java.util.AbstractMap.SimpleEntry;

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    
    Stack<SimpleEntry<TreeNode, Integer>> stack = new Stack<>();
    stack.push(new SimpleEntry<>(root, 1));
    int maxDepth = 0;
    
    while (!stack.isEmpty()) {
        SimpleEntry<TreeNode, Integer> entry = stack.pop();
        TreeNode node = entry.getKey();
        int currentDepth = entry.getValue();
        
        maxDepth = Math.max(maxDepth, currentDepth);
        
        // Push right first so left is processed first (matches recursive DFS order)
        if (node.right != null) stack.push(new SimpleEntry<>(node.right, currentDepth + 1));
        if (node.left != null) stack.push(new SimpleEntry<>(node.left, currentDepth + 1));
    }
    return maxDepth;
}

内容的提问来源于stack exchange，提问作者HbnKing