［抄題］：

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.?

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

Example 1:

Input: Tree 1 Tree 2 1 2 / \ / \ 3 2 1 3 / \ \ 5 4 7 Output: Merged tree:3/ \4 5/ \ \ 5 4 7

?[暴力解法]：

時(shí)間分析：

空間分析：

［奇葩輸出條件］：

［奇葩corner case］：

［思維問(wèn)題］：

以為要從上往下討論是否有空節(jié)點(diǎn)：實(shí)際上是討論不出來(lái)的，特殊情況要當(dāng)作corner case提前列出來(lái)，實(shí)現(xiàn)自動(dòng)判斷

［一句話(huà)思路］：

左邊和左邊融合，右邊和右邊融合

［輸入量］：空：?正常情況：特大：特小：程序里處理到的特殊情況：異常情況（不合法不合理的輸入）：

［畫(huà)圖］：

［一刷］：

出現(xiàn)新的數(shù)值就要新建一個(gè)節(jié)點(diǎn)：以前真不知道

左、右子樹(shù)情況不同時(shí)，分為node.left 和node.right兩邊去討論就行了，第二次見(jiàn)了應(yīng)該學(xué)會(huì)了

［二刷］：

［三刷］：

［四刷］：

［五刷］：

? [五分鐘肉眼debug的結(jié)果]：

［總結(jié)］：

［復(fù)雜度］：Time complexity: O(n) Space complexity: O(n)

［英文數(shù)據(jù)結(jié)構(gòu)或算法，為什么不用別的數(shù)據(jù)結(jié)構(gòu)或算法］：

左右討論還是用的traverse嵌套

［關(guān)鍵模板化代碼］：

//left & right :divide into node's left & node's rightnode.left = mergeTrees(t1.left, t2.left);node.right = mergeTrees(t1.right, t2.right);

［其他解法］：

［Follow Up］：

［LC給出的題目變變變］：

?[代碼風(fēng)格] ：

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/ class Solution {public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {//corner case:left is null or right is nullif (t1 == null) {return t2;}if (t2 == null) {return t1;}//left.val + right.val: new val needs new nodeTreeNode node = new TreeNode(t1.val + t2.val);//left & right :divide into node's left & node's rightnode.left = mergeTrees(t1.left, t2.left);node.right = mergeTrees(t1.right, t2.right);return node;} } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/immiao0319/p/8566678.html

總結(jié)

以上是生活随笔為你收集整理的17. Merge Two Binary Trees 融合二叉树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。