-
Notifications
You must be signed in to change notification settings - Fork 44
/
_617_mergeTrees.java
75 lines (71 loc) · 2.58 KB
/
_617_mergeTrees.java
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
package pp.arithmetic.leetcode;
import pp.arithmetic.Util;
import pp.arithmetic.model.TreeNode;
/**
* Created by wangpeng on 2019-09-20.
*
* 给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。
*
* 你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。
*
* 示例 1:
*
* 输入:
* Tree 1 Tree 2
* 1 2
* / \ / \
* 3 2 1 3
* / \ \
* 5 4 7
* 输出:
* 合并后的树:
* 3
* / \
* 4 5
* / \ \
* 5 4 7
* 注意: 合并必须从两个树的根节点开始。
*
* 来源:力扣(LeetCode)
* 链接:https://leetcode-cn.com/problems/merge-two-binary-trees
* 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
*/
public class _617_mergeTrees {
public static void main(String[] args) {
TreeNode treeNode1 = new TreeNode(1);
treeNode1.left = new TreeNode(3);
treeNode1.right = new TreeNode(2);
treeNode1.left.left = new TreeNode(5);
TreeNode treeNode2 = new TreeNode(2);
treeNode2.left = new TreeNode(1);
treeNode2.left.right = new TreeNode(4);
treeNode2.right = new TreeNode(3);
treeNode2.right.right = new TreeNode(7);
_617_mergeTrees mergeTrees = new _617_mergeTrees();
TreeNode treeNode = mergeTrees.mergeTrees(treeNode1, treeNode2);
Util.printTree(treeNode);
}
/**
* 解题思路:
* 对于数的题目基本是DFS递归
* 1、构建父节点,如t1、t2的不为null,使其加和
* 2、构建子树节点,将t2、t2对应位置传递过去,重复步骤1
*
* @param t1
* @param t2
* @return
*/
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) {
return null;
}
//1、构建父节点
TreeNode node = new TreeNode(0);
if (t1 != null) node.val += t1.val;
if (t2 != null) node.val += t2.val;
//2、构建子树节点
node.left = mergeTrees(t1 == null ? null : t1.left, t2 == null ? null : t2.left);
node.right = mergeTrees(t1 == null ? null : t1.right, t2 == null ? null : t2.right);
return node;
}
}