需求
给你两棵二叉树： root1 和 root2 。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
**注意: **合并过程必须从两个树的根节点开始。
示例：1
合并二叉树
输入： root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出： [3,4,5,5,4,null,7]
思路：
根据题目就是将两个二叉树进行合并，相同位置元素值进行相加后生成一个新的二叉树。
递归法：
递归法最简单的办法是使用前序遍历，获取中节点数据详见，在递归左右子节点数值相加。
层序遍历：
根据层进行遍历，利用其中一棵二叉树，作为返回值，将另一棵二叉树的值替换或者相加到当前二叉树。
/**
* 617. 合并二叉树
* 前序遍历
*/
public class MergeTrees617 {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null && root2 == null) return null;
int roo1Val = 0;
int root2Val = 0;
if (root1 != null) roo1Val = root1.val;
if (root2 != null) root2Val = root2.val;
TreeNode node = new TreeNode(roo1Val + root2Val); // 中
node.left = mergeTrees(
root1 == null ? null : root1.left
, root2 == null ? null : root2.left);// 左
node.right = mergeTrees(
root1 == null ? null : root1.right
, root2 == null ? null : root2.right);// 右
return node;
}
// 递归精简版本
public TreeNode mergeTreesJj(TreeNode root1, TreeNode root2) {
if (root1 == null) return root2;
if (root2 == null) return root1;
root1.val += root2.val;// 中
root1.left = mergeTrees(root1.left, root2.left);// 左
root1.right = mergeTrees(root1.right, root2.right);// 右
return root1;
}
/**
* 层序遍历
* 这个题的关键在于怎么关联第二层数据
* 利用其中一个二叉树，由第二个二叉树不起null位合并
*/
public TreeNode mergeTreesGd(TreeNode root1, TreeNode root2) {
if(root1 ==null) return root2;
if(root2==null) return root1;
Stack<TreeNode> stack = new Stack<>();
stack.push(root2);
stack.push(root1);
while (!stack.isEmpty()){
int size = stack.size();
while (size>0){// 这个while可以省略掉
size -=2;
TreeNode node1 = stack.pop();
TreeNode node2 = stack.pop();
node1.val+=node2.val;
if(node1.left !=null && node2.left!=null){
stack.push(node2.left);
stack.push(node1.left);
}else {
if(node1.left == null){
node1.left = node2.left;
}
}
if(node1.right!=null && node2.right!=null){
stack.push(node2.right);
stack.push(node1.right);
}else {
if(node1.right == null){
node1.right=node2.right;
}
}
}
}
return root1;
}
}
验证结果
