leetcode:617. 合并二叉樹 - 力扣（LeetCode）

題目

給定兩個二叉樹，想象當你將它們中的一個覆蓋到另一個上時，兩個二叉樹的一些節點便會重疊。

你需要將他們合并為一個新的二叉樹。合并的規則是如果兩個節點重疊，那么將他們的值相加作為節點合并后的新值，否則不為?NULL 的節點將直接作為新二叉樹的節點。

注意：合并必須從兩個數的根節點開始。?

思路

這題采用前序遞歸的方法，將兩棵樹對應的節點進行相加就可以了。

遞歸三部曲

（1）輸入的是兩棵樹t1、t2的根節點，返回的是新樹的根節點。

（2）如果t1=NULL，那么返回t2；如果t2=NULL，那么返回t1。

（3）將兩棵樹的元素加到一起，左子樹相加，右子樹相加。

代碼如下：

class Solution
{public:/*** 合并兩個二叉樹* 當兩個節點重疊時，將它們的值相加作為新節點的值* 如果一個節點為空，則返回另一個節點* 遞歸地對兩個樹的左子樹和右子樹進行合并* * @param t1 第一個二叉樹的根節點* @param t2 第二個二叉樹的根節點* @return 合并后的二叉樹的根節點*/TreeNode *mergeTrees(TreeNode *t1,TreeNode *t2){// 如果t1為空，直接返回t2if(t1==NULL) return t2;// 如果t2為空，直接返回t1if(t2==NULL) return t1;// 將兩個節點的值相加，作為新節點的值t1->val = t1->val + t2->val;// 遞歸合并左子樹t1->left = mergeTrees(t1->left,t2->left);// 遞歸合并右子樹t1->right = mergeTrees(t1->right,t2->right);// 返回合并后的樹的根節點return t1;}
};

總結

這題可以用很多種方法，不管前序、中序、后序，使用迭代法解決也很方便，二刷的時候我會全部補齊。

參考資料

?代碼隨想錄

一起操作兩個二叉樹？有點懵！| LeetCode：617.合并二叉樹_嗶哩嗶哩_bilibili?