617-合并二叉树

Doublew2w大约 3 分钟

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

示例 1：

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

示例 2：

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

提示：

两棵树中的节点数目在范围 [0, 2000] 内
-10 ⁴ <= Node.val <= 10 ⁴

思路：前序遍历

这道题理解起来很简单，但跟之前不同的是要操作两棵树。

对于相同节点位置，进行值合并。
如果一棵树为空，一个棵不为空，则进行移动即可。

使用「前序遍历」进行递归

递归函数定义：返回值是根点，参数是两棵待合并的树

public TreeNode mergeTrees(TreeNode root1, TreeNode root2)

递归终止条件：树 1 的节点为 null 或者树 2 的节点为 null
单层递归：
1. 将两个树的节点相加后，再赋给树 1 的节点。
2. 再递归的执行两个树的左节点
3. 递归执行两个树的右节点

代码


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
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);
        root.left = mergeTrees(root1.left,root2.left);
        root.right = mergeTrees(root1.right,root2.right);
        return root;
    }
}

复杂度分析

令 n1 为树 1 的节点个数，n2 为树 2 的节点个数。

时间复杂度： $O(min(n1,n2))$ , 两个二叉树同时进行深度优先搜索，只有当两个二叉树中的对应节点都不为空时才会对该节点进行显性合并操作。
空间复杂度： $O(min(n1,n2))$ ，空间复杂度取决于递归调用的层数，递归调用的层数不会超过较小的二叉树的最大高度

思路：迭代

只要两颗树的左节点都不为 null，就把将他们放入队列中；同理只要两棵树的右节点都不为 null 了，也将他们放入队列中。

不断的从队列中取出节点，把他们相加。

如果树 2 的 left 节点不为 null，而树 1 的 left 节点为 null，则直接将树 2 的 left 赋给树 1
如果树 2 的 right 节点不为 null，而树 1 的 right 节点为 null，则直接将树 2 的 right 赋给树 1

代码

class Solution {
	public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
	//如果 t1 和 t2 中，只要有一个是 null，函数就直接返回
		if(t1==null || t2==null) {
			return t1==null? t2 : t1;
		}
		java.util.LinkedList<TreeNode> queue = new java.util.LinkedList<TreeNode>();
		queue.add(t1);
		queue.add(t2);
		while(queue.size()>0) {
			TreeNode r1 = queue.remove();
			TreeNode r2 = queue.remove();
			r1.val += r2.val;
			//如果 r1 和 r2 的左子树都不为空，就放到队列中
			//如果 r1 的左子树为空，就把 r2 的左子树挂到 r1 的左子树上
			if(r1.left!=null && r2.left!=null){
				queue.add(r1.left);
				queue.add(r2.left);
			}
			else if(r1.left==null) {
				r1.left = r2.left;
			}
			//对于右子树也是一样的
			if(r1.right!=null && r2.right!=null) {
				queue.add(r1.right);
				queue.add(r2.right);
			}
			else if(r1.right==null) {
				r1.right = r2.right;
			}
		}
		return t1;
	}
}

617-合并二叉树

题目地址(617. 合并二叉树 - 力扣（LeetCode）)

题目描述

思路：前序遍历

代码

思路：迭代

代码