617. 合并二叉树
给你两棵二叉树： root1 和 root2 。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
[思路]
递归
1、确定递归函数的参数和返回值：
首先要合入两个二叉树，那么参数至少是传入两个二叉树的根节点，返回值就是合并之后二叉树的根节点。
TreeNode merageTrees(TreeNode t1, TreeNode t2){}
2、确定终止条件：
因为是传入了两个树，那么就有两个树遍历的节点t1 和 t2，如果t1 == NULL 了，两个树合并就应该是 t2 了（如果t2也为NULL也无所谓，合并之后就是NULL）。
反过来如果t2 == NULL，那么两个数合并就是t1（如果t1也为NULL也无所谓，合并之后就是NULL）。
if (t1 == NULL) return t2; // 如果t1为空，合并之后就应该是t2 if (t2 == NULL) return t1; // 如果t2为空，合并之后就应该是t1
3、确定单层递归的逻辑：
单层递归的逻辑就是重复利用t1这个树，t1就是合并之后树的根节点（就是修改了原来树的结构）。
单层递归中，就是把两颗树的元素加到一起。
t1.val += t2.val;
接下来t1的左子树是：合并t1左子树 t2左子树之后的左子树
t1的右子树是：合并t1右子树 t2右子树之后的右子树
最终t1就是合并之后的根节点。
代码如下：
t1.left = mergeTrees(t1.left, t2.left); t1.right = mergeTrees(t1.right, t2.right); return t1;
前序遍历整体代码如下：
class Solution { TreeNode mergeTrees(TreeNode t1, TreeNode t2) { if (t1 == NULL) return t2; // 如果t1为空，合并之后就应该是t2 if (t2 == NULL) return t1; // 如果t2为空，合并之后就应该是t1 // 修改了t1的数值和结构 t1.val += t2.val; // 中 t1.left = mergeTrees(t1.left, t2.left); // 左 t1.right = mergeTrees(t1.right, t2.right); // 右 return t1; } }
class Solution { TreeNode mergeTrees(TreeNode t1, TreeNode t2) { if (t1 == NULL) return t2; // 如果t1为空，合并之后就应该是t2 if (t2 == NULL) return t1; // 如果t2为空，合并之后就应该是t1 // 修改了t1的数值和结构 t1.val += t2.val; // 中 t1.left = mergeTrees(t1.left, t2.left); // 左 t1.right = mergeTrees(t1.right, t2.right); // 右 return t1; } }
中序遍历：
class Solution { TreeNode mergeTrees(TreeNode t1, TreeNode t2) { if (t1 == NULL) return t2; // 如果t1为空，合并之后就应该是t2 if (t2 == NULL) return t1; // 如果t2为空，合并之后就应该是t1 // 修改了t1的数值和结构 t1.left = mergeTrees(t1.left, t2.left); // 左 t1.val += t2.val; // 中 t1.right = mergeTrees(t1.right, t2.right); // 右 return t1; } }
后序遍历：
class Solution { TreeNode mergeTrees(TreeNode t1, TreeNode t2) { if (t1 == NULL) return t2; // 如果t1为空，合并之后就应该是t2 if (t2 == NULL) return t1; // 如果t2为空，合并之后就应该是t1 // 修改了t1的数值和结构 t1.left = mergeTrees(t1.left, t2.left); // 左 t1.right = mergeTrees(t1.right, t2.right); // 右 t1.val += t2.val; // 中 return t1; } }
本题使用前、中、后序遍历都可以。
若不改变t1的结构，当然也可以不修改t1和t2的结构，重新定义一个树。
不修改输入树的结构，前序遍历，代码如下：
class Solution { TreeNode mergeTrees(TreeNode t1, TreeNode t2) { if (t1 == null) return t2; if (t2 == null) return t1; //重新定义新的节点，不修改原有两个树的结构 TreeNode root = new TreeNode(0); root.val = t1.val + t2.val; root.left = mergeTrees(t1.left, t2.left); root.right = mergeTrees(t1.right, t2.right); return root; } }
迭代法：
class Solution { //使用栈迭代 public TreeNode mergeTrees(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()) { TreeNode node1 = stack.pop(); TreeNode node2 = stack.pop(); node1.val += node2.val; if (node2.right != null && node1.right != null) { stack.push(node2.right); stack.push(node1.right); } else { if (node1.right == null) { node1.right = node2.right; } } if (node2.left != null && node1.left != null) { stack.push(node2.left); stack.push(node1.left); } else { if (node1.left == null) { node1.left = node2.left; } } } return root1; } }
