1. 題目
描述
已知兩顆二叉樹，將它們合併成一顆二叉樹。合併規則是：都存在的結點，就將結點值加起來，否則空的位置就由另一個樹的結點來代替。例如：
數據範圍：樹上節點數量滿足 0 ≤n≤500，樹上節點的值一定在32位整型範圍內。
進階：空間複雜度 O(1) ，時間複雜度 O(n)
示例1
輸入：
{1,3,2,5},{2,1,3,#,4,#,7}返回值：
{3,4,5,5,4,#,7}示例2
輸入：
{1},{}返回值：
{1}2. 解題思路
二叉樹tree1與tree2的合併，我們可以將tree2合併到tree1，採用遞歸方法。具體操作為：
tree1的節點值為兩顆二叉樹節點值的和：t1.val=t1.val+t2.val;
tree1的新生成的左子樹為：tree1的左子樹和tree2的左子樹合併的結果；
tree1的新生成的右子樹為：tree1的右子樹和tree2的右子樹合併的結果。
先來看看二叉樹的合併是否滿足遞歸條件：
可以看出，二叉樹的合併滿足遞歸的兩個條件，因此可以通過遞歸來實現二叉樹的合併。我們將tree2合併到tree1，採用遞歸方法。具體操作為：
tree1的節點值為兩顆二叉樹節點值的和：t1.val=t1.val+t2.val;
tree1的新生成的左子樹為：tree1的左子樹和tree2的左子樹合併的結果；
tree1的新生成的右子樹為：tree1的右子樹和tree2的右子樹合併的結果。
對應的遞推公式如下：
有了遞推公式，就可以很方便的寫出代碼。tree1與tree2合併之後，新生成的二叉樹如下所示：
如果文字描述的不太清楚，你可以參考視頻的詳細講解。
- Python版本：https://www.bilibili.com/cheese/play/ep1372109
- Java版本：https://www.bilibili.com/cheese/play/ep1367348
- Golang版本：https://www.bilibili.com/cheese/play/ep1364773
3. 編碼實現
核心代碼如下：
/**
* 代碼中的類名、方法名、參數名已經指定，請勿修改，直接返回方法規定的值即可
*
*
* @param t1 TreeNode類
* @param t2 TreeNode類
* @return TreeNode類
*/
func mergeTrees(t1 *TreeNode, t2 *TreeNode) *TreeNode {
// write code here
// 2. 遞歸終止條件
if t1 == nil && t2 == nil {
return nil
}
// 2.2 當前節點為空，則返回另外一個節點
if t1 == nil && t2 != nil {
return t2
}
if t1 != nil && t2 == nil {
return t1
}
// 1. 問題分解（遞推公式）
// 1.1 root節點處理（將t2合併到t1）,兩個節點的值求和並賦給t1
t1.Val = t1.Val + t2.Val
// 1.2 合併t1、t2的左節點
t1.Left = mergeTrees(t1.Left, t2.Left)
// 1.3 合併t1、t2的右節點
t1.Right = mergeTrees(t1.Right, t2.Right)
return t1
}具體完整代碼你可以參考下面視頻的詳細講解。
- Python版本：https://www.bilibili.com/cheese/play/ep1372109
- Java版本：https://www.bilibili.com/cheese/play/ep1367348
- Golang版本：https://www.bilibili.com/cheese/play/ep1364773
4.小結
二叉樹tree1與tree2的合併，我們可以將tree2合併到tree1，採用遞歸方法。具體操作為：
tree1的節點值為兩顆二叉樹節點值的和：t1.val=t1.val+t2.val;
tree1的新生成的左子樹為：tree1的左子樹和tree2的左子樹合併的結果；
tree1的新生成的右子樹為：tree1的右子樹和tree2的右子樹合併的結果。
《數據結構與算法》深度精講課程正式上線啦！七大核心算法模塊全解析：
✅ 鏈表
✅ 二叉樹
✅ 二分查找、排序
✅ 堆、棧、隊列
✅ 回溯算法
✅ 哈希算法
✅ 動態規劃
無論你是備戰筆試面試、提升代碼效率，還是突破技術瓶頸，這套課程都將為你構建紮實的算法思維底座。🔥立即加入學習打卡，與千名開發者共同進階！
- Python編碼實現：https://www.bilibili.com/cheese/play/ss897667807
- Java編碼實現：https://www.bilibili.com/cheese/play/ss161443488
- Golang編碼實現：https://www.bilibili.com/cheese/play/ss63997
對於二叉樹的相關算法，我們總結了一套【可視化+圖解】方法，依據此方法來解決相關問題，算法變得易於理解，寫出來的代碼可讀性高也不容易出錯。具體也可以參考視頻詳細講解。
今日佳句：十年身事各如萍，白首相逢淚滿纓。
