題目描述:給定兩棵二元樹 root1 和 root2,將它們合併成一棵新的二元樹。合併規則是:若兩棵樹的對應節點都存在,新節點的值為兩者之和;若其中一棵樹的節點為空,新樹使用另一棵樹的節點。
解題思路:使用遞迴同時遍歷兩棵樹。對於每個位置:
root1(原地修改),然後遞迴處理左右子樹。這種方法直接修改 root1,不需要額外建立新節點。
時間複雜度:O(min(m, n)) — m 和 n 分別為兩棵樹的節點數,只需遍歷兩棵樹重疊的部分。
空間複雜度:O(min(m, n)) — 遞迴深度取決於較小的樹的高度,最壞情況為 O(min(m, n))。
1. If root1 is null, return root2 2. If root2 is null, return root1 3. root1.val += root2.val 4. root1.left = mergeTrees(root1.left, root2.left) 5. root1.right = mergeTrees(root1.right, root2.right) 6. Return root1
建立新樹:不修改原樹,每次建立新的 TreeNode。時間空間複雜度相同,但不會破壞輸入資料,適合需要保留原樹的場景。
迭代法(BFS):用佇列同時遍歷兩棵樹的對應節點。時間複雜度 O(min(m, n)),空間複雜度 O(min(m, n))。適合樹很深但不想使用遞迴的場景。