題目來源:力扣(LeetCode)
鏈接:https://leetcode-cn.com/problems/merge-two-binary-trees
給定兩個(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)弃酌。
示例 1:
輸入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
輸出:
合并后的樹:
3
/ \
4 5
/ \ \
5 4 7
注意: 合并必須從兩個(gè)樹的根節(jié)點(diǎn)開始土榴。
遞歸解法:
/**
* 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) {
if(t1 == null)
return t2;
if(t2 == null)
return t1;
TreeNode root = new TreeNode(t1.val+t2.val);
root.left = mergeTrees(t1.left,t2.left);
root.right = mergeTrees(t1.right,t2.right);
return root;
}
}