两种Java二叉树镜像方法的时间与空间复杂度优劣对比咨询

Great question—let's break down how your two mirror image implementations stack up in terms of time and space complexity, plus cover their practical tradeoffs.

First, let's recap the two approaches with your code:

Way 1: In-Place Mirror (Your Implementation) #

public static TreeNode mirrorImage (TreeNode t) {
 if (t == null) return null;
 TreeNode right = t.getRight();
 TreeNode left = t.getLeft();
 t.setLeft(mirrorImage(right));
 t.setRight(mirrorImage(left));
 return t;
}

Way 2: New Tree Mirror (Teacher's Implementation) #

public static TreeNode mirrorImage (TreeNode t) {
 if (t == null) return null;
 else return new TreeNode (t.getValue(), mirrorImage(t.getRight()), mirrorImage(t.getLeft()));
}

Time Complexity: Both O(n) #

Both methods have identical time complexity of O(n), where n is the number of nodes in the tree. Here's why:

• Every node in the tree is processed exactly once. For Way 1, we swap the left/right pointers of each node. For Way 2, we create a new node for each existing node.
• Recursion just traverses each node in a depth-first manner—no extra loops or repeated processing, so the time scales linearly with the number of nodes.

Space Complexity: Key Difference Here #

This is where the two methods diverge significantly:

Way 1: O(h) Space (h = tree height) #

• Since this is an in-place modification, we don't allocate any new TreeNode instances. The only extra space comes from the recursion call stack.
• The stack depth equals the height of the tree (h):
  • For a balanced tree, h = log n, so space complexity is O(log n).
  • For a skewed tree (like a linked list), h = n, so space complexity is O(n).
• Pro: Minimal memory overhead—we reuse the existing tree structure.
• Con: The original tree is permanently modified (its left/right pointers are swapped).

Way 2: O(n) Space #

• This method creates a brand new TreeNode for every node in the original tree, so we immediately allocate O(n) space for the new tree itself.
• On top of that, we still have the recursion call stack space (O(h)), but since O(n) dominates O(h), the overall space complexity is O(n).
• Pro: The original tree remains completely untouched—great if you need to keep the original structure intact.
• Con: Uses significantly more memory, especially for large trees, since you're duplicating every node.

Practical Tradeoffs to Consider #

• Use Way 1 when: You don't need the original tree anymore, and want to save memory. This is the more memory-efficient choice.
• Use Way 2 when: You need to preserve the original tree, or when you want a clean, functional-style implementation (no side effects on the input).

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