369 字
2 分钟
算法之合并二叉树
617. 合并二叉树
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
思路
-
同步地遍历两棵树上的节点，直接在 t1 上修改。
如果把 mergeTrees 函数作为递归函数，参数 t1 和 t2 是指：当前遍历的节点（子树）
递归。总是关注当前节点 t1 为 null 、t2 不是 null，t1t1 换成 t2 。（return t2） t2 为 null、t1t1 不是 null，t1t1 依然 t1 。（return t1）
t1 和 t2 都为 null，t1t1 依然 t1。（return t1）
t1、t2 都存在，将 t2 的值加给 t1 。（t1.val += t2.val）
『子树的合并』交给递归去做，它会对每一个节点做同样的事情。
t1.left = mergeTrees(t1.left, t2.left);t1.right = mergeTrees(t1.right, t2.right);
代码
const mergeTrees = (t1, t2) => { if (t1 == null && t2) { return t2; } if ((t1 && t2 == null) || (t1 == null && t2 == null)) { return t1; } t1.val += t2.val;
t1.left = mergeTrees(t1.left, t2.left); t1.right = mergeTrees(t1.right, t2.right);
return t1;};如果不在原树修改，新建一个树呢？
const mergeTrees = (t1, t2) => { if (t1 == null && t2) { return t2; } if ((t1 && t2 == null) || (t1 == null && t2 == null)) { return t1; } const root=new TreeNode(t1.val + t2.val)
root.left = mergeTrees(t1.left, t2.left); root.right = mergeTrees(t1.right, t2.right);
return root;};