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;
    }
}