九旬的博客

描述

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为  NULL 的节点将直接作为新二叉树的节点。

示例  1:

输入:

	Tree 1                     Tree 2
          1                         2
         / \                       / \
        3   2                     1   3
       /                           \   \
      5                             4   7
1
2
3
4
5
6

输出:
合并后的树:

	     3
	    / \
	   4   5
	  / \   \
	 5   4   7
1
2
3
4
5

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

题目链接：合并二叉树open in new window

解法

因为 JS 没有二叉树的数据结构，所以新建了一个 TreeNode 的 Class，发现用 TS 写真香...

//Definition for a binary tree node.
class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}
1
2
3
4
5
6
7
8
9
10
11

递归

function mergeTrees(
  root1: TreeNode | null,
  root2: TreeNode | null
): TreeNode | null {
  // root2 有值 返回root2
  if (root1 === null && root2) {
    return root2;
  }
  // root2 没值 返回root1
  if ((root1 && root2 === null) || (root1 === null && root2 === null)) {
    return root1;
  }
  // 都有值的情况 合并
  root1.val = root1.val + root2.val;
  root1.left = mergeTrees(root1.left, root2.left);
  root1.right = mergeTrees(root1.right, root2.right);
  return root1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

复杂度分析

  • 时间复杂度：O(n)。
  • 空间复杂度：O(n)。

总结

二叉树，无脑递归，先总结出一个节点的要做的事情的规律，然后让所有的节点都去做同样的事情。