617. 合并二叉樹
給定兩個(gè)二叉樹罚攀，想象當(dāng)你將它們中的一個(gè)覆蓋到另一個(gè)上時(shí)暖哨，兩個(gè)二叉樹的一些節(jié)點(diǎn)便會(huì)重疊笆包。
你需要將他們合并為一個(gè)新的二叉樹。合并的規(guī)則是如果兩個(gè)節(jié)點(diǎn)重疊腊尚，那么將他們的值相加作為節(jié)點(diǎn)合并后的新值吨拗，否則不為 NULL 的節(jié)點(diǎn)將直接作為新二叉樹的節(jié)點(diǎn)。
示例:
輸入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
輸出:
合并后的樹:
3
/ \
4 5
/ \ \
5 4 7
注意:
- 合并必須從兩個(gè)樹的根節(jié)點(diǎn)開始。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/merge-two-binary-trees/
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有劝篷。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)哨鸭，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
-
創(chuàng)建二叉搜索樹
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
-
1. 遞歸法
思路：
- 遞歸終止條件為兩個(gè)樹中某個(gè)節(jié)點(diǎn)為空娇妓，返回那個(gè)不為空的節(jié)點(diǎn)即可
- 計(jì)算節(jié)點(diǎn)之和
- 使用遞歸一次計(jì)算左右子樹
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null) return t2;
if (t2 == null) return t1;
//先計(jì)算節(jié)點(diǎn)之和
TreeNode result = new TreeNode(t1.val + t2.val);
result.left = mergeTrees(t1.left, t2.left);
result.right = mergeTrees(t1.right, t2.right);
return result;
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：O(n), 每個(gè)元素都被訪問了一次
- 空間復(fù)雜度：O(n)
-
源碼
-
我會(huì)每天更新新的算法像鸡，并盡可能嘗試不同解法，如果發(fā)現(xiàn)問題請(qǐng)指正
- Github
