617. 合併二元樹

題目描述

給定兩棵二元樹 root1 和 root2，將它們合併成一棵新樹。合併規則：若兩節點重疊則相加；否則使用非空節點作為新樹節點。

解法思路

1. 同步遞迴兩棵樹，每次處理 (root1, root2) 這對節點
2. 若 root1 為 None，直接回傳 root2（嫁接整棵子樹）
3. 若 root2 為 None，直接回傳 root1（保留不變）
4. 兩者都存在：root1.val += root2.val，遞迴合併左右子樹
5. 回傳修改後的 root1

複雜度分析

• 時間複雜度：O(min(n1,n2))
• 空間複雜度：O(min(h1,h2))，h 為樹的高度