跃迁引擎

空気を読んだ雨降らないでよ

iOS Research & Development


合并二叉树

LeetCode 617 合并二叉树

题目

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

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

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入: 
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/ \
4 5
/ \ \
5 4 7

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

题解

这题思路比较直接,直接从根节点开始合并相加左右节点的值就可以了,根节点合并后,再开始递归合并左右子节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null) {
return t2;
}
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;
}
}
最近的文章

为一台 macOS 新设备快速配置基本开发环境的最佳实践(避坑)指南

本文将提供一套最佳实践流,来帮助你告别 macOS 裸机配置开发环境时的各种坑,告别痛苦,一发入魂 …

, , 开始阅读
更早的文章

翻转二叉树

谷歌:我们90%的工程师使用您编写的软件(Homebrew),但是您却无法在面试时在白板上写出翻转二叉树这道题,这太糟糕了。 …

, , 开始阅读
comments powered by Disqus