【Go 刷leetcode】合并二叉樹
今天為大家講解 LeetCode 第 617 題，是一道關于二叉樹的簡單的題目。
題目描述?
給定兩個二叉樹，想象當你將它們中的一個覆蓋到另一個上時，兩個二叉樹的一些節(jié)點便會重疊。
你需要將他們合并為一個新的二叉樹。合并的規(guī)則是如果兩個節(jié)點重疊，那么將他們的值相加作為節(jié)點合并后的新值，否則不為 NULL 的節(jié)點將直接作為新二叉樹的節(jié)點。
示例 1:
輸入: Tree 1 ? ? ? ? ? ? ? ? ? ? Tree 2
1 ? ? ? ? ? ? ? ? ? ? ? ? 2
/ \ ? ? ? ? ? ? ? ? ? ? ? / \
3 ? 2 ? ? ? ? ? ? ? ? ? ? 1 ? 3
/ ? ? ? ? ? ? ? ? ? ? ? ? ? \ ? \
5 ? ? ? ? ? ? ? ? ? ? ? ? ? ? 4 ? 7
輸出: 合并后的樹: 3 /
4 ? 5 / \ ? \ 5 ? 4 ? 7 注意: 合并必須從兩個樹的根節(jié)點開始。來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/merge-two-binary-trees 著作權歸領扣網(wǎng)絡所有。商業(yè)轉載請聯(lián)系官方授權，非商業(yè)轉載請注明出處。
解題思路
不難想到，我們可以從兩棵樹的根節(jié)點同時遍歷，并將對應的節(jié)點進行合并。
在遍歷時，如果兩棵樹的當前節(jié)點均不為空，我們就將它們的值進行相加，并對它們的左孩子和右孩子進行遞歸合并；如果其中有一棵樹為空，那么我們返回另一顆樹作為結果；如果兩棵樹均為空，此時返回任意一棵樹均可（因為都是空）。
代碼實現(xiàn)
//?go
func?mergeTrees(t1?*TreeNode,?t2?*TreeNode)?*TreeNode?{
?if?t1?==?nil?{
??return?t2
?}
?if?t2?==?nil?{
??return?t1
?}
?t1.Val?+=?t2.Val
?t1.Left?=?mergeTrees(t1.Left,?t2.Left)
?t1.Right?=?mergeTrees(t1.Right,?t2.Right)
?return?t1
}
//?java
public?class?Solution?{
????public?TreeNode?mergeTrees(TreeNode?t1,?TreeNode?t2)?{
????????if?(t1?==?null)
????????????return?t2;
????????if?(t2?==?null)
????????????return?t1;
????????t1.val?+=?t2.val;
????????t1.left?=?mergeTrees(t1.left,?t2.left);
????????t1.right?=?mergeTrees(t1.right,?t2.right);
????????return?t1;
????}
}
鄭重聲明：
所展示代碼已通過 LeetCode 運行通過，請放心食用～
推薦閱讀