合并二叉树【LC617】
给你两棵二叉树： root1 和 root2 。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/merge-two-binary-trees
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
- 思路
如果一个节点为空，那么直接返回另一个节点，无需进行合并；否则将值相加，得到合并的节点。该过程是个重复的子问题，因此可以使用dfs递归解决，注意：每次合并后需要更新合并后的节点 - 实现：dfs
class Solution { public TreeNode mergeTrees(TreeNode root1, TreeNode root2) { TreeNode root = new TreeNode(); if (root1 == null && root2 == null){ return null; }else if (root1 == null){ root = root2; }else if (root2 == null){ root = root1; }else{ root.val = root1.val + root2.val; root.left = mergeTrees(root1.left,root2.left); root.right = mergeTrees(root1.right,root2.right); } return root; } }
class Solution { public TreeNode mergeTrees(TreeNode t1, TreeNode t2) { if (t1 == null) { return t2; } if (t2 == null) { return t1; } TreeNode merged = new TreeNode(t1.val + t2.val); merged.left = mergeTrees(t1.left, t2.left); merged.right = mergeTrees(t1.right, t2.right); return merged; } } 作者：LeetCode-Solution 链接：https://leetcode.cn/problems/merge-two-binary-trees/solution/he-bing-er-cha-shu-by-leetcode-solution/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
BFS
如果两棵树某个节点的孩子节点都不为空，才需要将值相加，进行合并；如果有一个孩子节点为空，直接赋值将子树复制即可
class Solution { // 使用队列迭代 public TreeNode mergeTrees(TreeNode root1, TreeNode root2) { if (root1 == null) return root2; if (root2 ==null) return root1; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root1); queue.offer(root2); while (!queue.isEmpty()) { TreeNode node1 = queue.poll(); TreeNode node2 = queue.poll(); // 此时两个节点一定不为空，val相加 node1.val = node1.val + node2.val; // 如果两棵树左节点都不为空，加入队列 if (node1.left != null && node2.left != null) { queue.offer(node1.left); queue.offer(node2.left); } // 如果两棵树右节点都不为空，加入队列 if (node1.right != null && node2.right != null) { queue.offer(node1.right); queue.offer(node2.right); } // 若node1的左节点为空，直接赋值 if (node1.left == null && node2.left != null) { node1.left = node2.left; } // 若node2的左节点为空，直接赋值 if (node1.right == null && node2.right != null) { node1.right = node2.right; } } return root1; } }
