LeetCode 344 Merge Two Binary Trees

题意

合并两颗二叉树, 合并规则是相同位置的值进行相加, 返回生成后二叉树的根节点.

例 :

1
2
3
4
5
6
7
8
9
10
11
12
13
输入: 
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
3
/ \
4 5
/ \ \
5 4 7

解法

基本思路是将两棵树, 合并到左树上, 基本规则是只有当 tree1tree2 相同位置的节点都不为空时, 才能进行相加操作, 当 tree1 为空时, 把 tree2 的节点嫁接过来, 当 tree2 为空时, 保留 tree1 即可. 以此类推, 把每个节点都看成根节点即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null) {
return t2;
} else if (t2 == null) {
return t1;
}

t1.val += t2.val;
t1.left = mergeTrees(t1.left, t2.left);
t1.right = mergeTrees(t1.right, t2.right);
return t1;
}
}

Runtime: 0 ms, faster than 100.00% of Java online submissions for Merge Two Binary Trees.
Memory Usage: 41.2 MB, less than 78.32% of Java online submissions for Merge Two Binary Trees.

  • 本文作者: 赵俊
  • 本文链接: http://www.zhaojun.im/leetcode-617/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!