💬 Discord
Sign In
NeetCode #393LC-617EasyTrees
← Back to All Problems

#393 · #617 · Merge Two Binary Trees(合并二叉树)

📌 Problem Statement & Constraints

You are given two binary trees root1 and root2. Merge them: where both nodes exist, the merged value is their sum; otherwise the existing node is used. Return the merged tree. Constraints: the number of nodes in each tree is in [0, 2000], -10^4 <= Node.val <= 10^4.

💡 Core Algorithmic Approaches

  1. Recurse on the two trees in parallel.
  2. If one side is None, return the other side directly -- no further work is needed there.
  3. Otherwise add the values and recurse on both children, reusing root1 as the merged node.
  4. This is O(min(n, m)) in the best case and O(n + m) in the worst.

💻 Benchmark Python3 Implementation

class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root1:
            return root2                   # nothing to merge on this side
        if not root2:
            return root1
        root1.val += root2.val             # reuse root1 as the merged node
        root1.left = self.mergeTrees(root1.left, root2.left)
        root1.right = self.mergeTrees(root1.right, root2.right)
        return root1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(min(n, m)) for the overlapping part plus O(1) for the shared subtrees.
💾 Space Complexity
O(h) for the recursion stack.

⚠️ Interview Pitfalls & Follow-ups

  • Mutating root2 instead: either is acceptable, but mutating one input should be a deliberate choice. Here root1 is reused.
  • Forgetting the None short-circuits: without them, the recursion would fail on None.val.
  • Creating new nodes for the shared subtrees: unnecessary work; the existing subtrees can be attached directly.
  • Assuming the trees have the same shape: they generally do not, which the short-circuits handle.