?歡迎訂閱《leetcode》專欄，每日一題，每天進步?
遞回就完事了，， 大一菜雞艱難刷題中，，
——leetcode此題熱評
前言
哈嘍，大家好，我是一條，
糊涂演算法，難得糊涂
簡單題倒數第二道！
Question
617. 合并二叉樹
難度：簡單
給定兩個二叉樹，想象當你將它們中的一個覆寫到另一個上時，兩個二叉樹的一些節點便會重疊，
你需要將他們合并為一個新的二叉樹，合并的規則是如果兩個節點重疊，那么將他們的值相加作為節點合并后的新值，否則不為 NULL 的節點將直接作為新二叉樹的節點，
示例 1:
注意: 合并必須從兩個樹的根節點開始，
Solution
就像評論說的，遞回少不了，
如果沒有頭緒的話，可以將這兩顆樹想象成是兩個陣列
-
終止條件：樹 1 或者樹 2 的節點為
null -
遞回函式內：將兩個樹的節點相加，再遞回的執行兩個樹的左節點，遞回執行兩個樹的右節點
🤔思考一下如何不利用額外空間？
Code
所有
leetcode代碼已同步至github歡迎
star
/**
* @author yitiaoIT
*/
class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null) {
return t2;
}
if (t2 == null) {
return t1;
}
TreeNode merged = new TreeNode(t1.val + t2.val);
merged.left = mergeTrees(t1.left, t2.left);
merged.right = mergeTrees(t1.right, t2.right);
return merged;
}
}
Result
復雜度分析
- 時間復雜度：O(N)
🌈尋寶
?今天是堅持刷題更文的第29/100天
?各位的點贊、關注、收藏、評論、訂閱就是一條創作的最大動力
?更多演算法題歡迎關注專欄《leetcode》
為了回饋各位粉絲，禮尚往來，給大家準備了一條多年積累下來的優質資源，包括 學習視頻、面試資料、珍藏電子書等
大家可以先自己找一下獲取方式，尋寶游戲現在開始，
如果實在找不到可以評論區留言或私信我領取，不過一定要先關注哦！不然無法發私信！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/294056.html
標籤：其他
上一篇：C實作三子棋及bug解決方法