4徐汇区网站建设/宁波seo智能优化

题目

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

示例

输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]

输入：root1 = [1], root2 = [1,2]
输出：[2,2]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/merge-two-binary-trees
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法1：递归

Java实现

class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {TreeNode root = new TreeNode();if (root1 == null) return root2;if (root2 == null) return root1;if (root1 != null && root2 != null){root.val = root1.val + root2.val;}root.left = mergeTrees(root1.left, root2.left);root.right = mergeTrees(root1.right, root2.right);return root;}
}

方法2：BFS

Java实现

class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if (root1 == null) return root2;if (root2 == null) return root1;TreeNode root = new TreeNode(root1.val + root2.val);Queue<TreeNode> q = new LinkedList<>();Queue<TreeNode> q1 = new LinkedList<>();Queue<TreeNode> q2 = new LinkedList<>();q.offer(root);q1.offer(root1);q2.offer(root2);while (!q1.isEmpty() && !q2.isEmpty()) {TreeNode node = q.poll(), node1 = q1.poll(), node2 = q2.poll();TreeNode left1 = node1.left, right1 = node1.right;TreeNode left2 = node2.left, right2 = node2.right;if (left1 != null || left2 != null) {if (left1 != null && left2 != null) {TreeNode left = new TreeNode(left1.val + left2.val);node.left = left;q.offer(left);q1.offer(left1);q2.offer(left2);} else if (left1 == null) {node.left = left2;} else if (left2 == null) {node.left = left1;}}if (right1 != null || right2 != null) {if (right1 != null && right2 != null) {TreeNode right = new TreeNode(right1.val + right2.val);node.right = right;q.offer(right);q1.offer(right1);q2.offer(right2);} else if (right1 == null) {node.right = right2;} else if (right2 == null) {node.right = right1;}}}return root;}
}