题目
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
示例 1:
输入: Tree 1 Tree 2 1 2 / \ / \ 3 2 1 3 / \ \ 5 4 7 输出: 合并后的树: 3 / \ 4 5 / \ \ 5 4 7
注意: 合并必须从两个树的根节点开始。
解答
方法一：递归
python解法
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode: if not root1: return root2 if not root2: return root1 root1.val+=root2.val root1.left = self.mergeTrees(root1.left,root2.left) root1.right = self.mergeTrees(root1.right,root2.right) return root1
c++解法
class Solution { public: TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) { if(!root1) return root2; if(!root2) return root1; root1->val+=root2->val; root1->left=mergeTrees(root1->left,root2->left); root1->right=mergeTrees(root1->right,root2->right); return root1; } };
java解法
class Solution { public TreeNode mergeTrees(TreeNode root1, TreeNode root2) { if(root1==null&&root2==null) return null; if(root1==null||root2==null) return root1!=null?root1:root2; root1.val+=root2.val; root1.left=mergeTrees(root1.left,root2.left); root1.right=mergeTrees(root1.right,root2.right); return root1; } }
方法二：迭代
python解法
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode: if not root1: return root2 if not root2: return root1 queue = collections.deque() queue.append(root1) queue.append(root2) while queue: node1 = queue.popleft() node2 = queue.popleft() # 只对都存在的加入队列中 if node1.left and node2.left: queue.append(node1.left) queue.append(node2.left) if node1.right and node2.right: queue.append(node1.right) queue.append(node2.right) node1.val+=node2.val # 只要有一个不存在，那么子树就是另一个存在的(因为返回的是root1，所以不需要考虑node1.left存在,node2.left不存在的情况) if not node1.left and node2.left node1.left = node2.left if not node1.right and node2.right: node1.right = node2.right return root1
c++解法
class Solution { public: TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) { if(!root1) return root2; if(!root2) return root1; queue<TreeNode*> queue; queue.push(root1); queue.push(root2); while(!queue.empty()){ TreeNode* node1=queue.front(); queue.pop(); TreeNode* node2=queue.front(); queue.pop(); node1->val+=node2->val; if(node1->left&&node2->left){ queue.push(node1->left); queue.push(node2->left); } if(node1->right&&node2->right){ queue.push(node1->right); queue.push(node2->right); } if(!node1->left) node1->left=node2->left; if(!node1->right) node1->right=node2->right; } return root1; } };
