0%

相同的树


题目描述

给定两个二叉树,编写一个函数来检验它们是否相同。如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

示例 1:

1
2
3
4
5
6
7
8
9
输入:

1 1
/ \ / \
2 3 2 3

[1, 2, 3], [1, 2, 3]

输出: true

示例 2:

1
2
3
4
5
6
7
8
9
输入:

1 1
/ \
2 2

[1, 2], [1, null, 2]

输出: false

示例 3:

1
2
3
4
5
6
7
8
9
输入:

1 1
/ \ / \
2 1 1 2

[1, 2, 1], [1, 1, 2]

输出: false

题解

此题是另外一道题的一个子解题步骤:另一个树的子树,根据题目描述,我们可以使用深度优先搜索,首先判断如果两个二叉树都为空,则两个二叉树相同。如果两个二叉树中有且只有一个为空,则两个二叉树一定不相同【这也是递归的终止条件】。然后判断两个树的根节点值是否相同,接下来递归的方式处理两个树的左子树和右子树,如果都相同,则为相同的树。

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
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null || q == null) {
return p == null && q == null;
} else {
return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}

public class TreeNode {
int val;
TreeNode left;
TreeNode right;

TreeNode() {
}

TreeNode(int val) {
this.val = val;
}

TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}

复杂度分析

  • 时间复杂度:O(min(m, n)),其中 m 和 n 分别是两个二叉树的节点数。对两个二叉树同时进行深度优先搜索,只有当两个二叉树中的对应节点都不为空时才会访问到该节点,因此被访问到的节点数不会超过较小的二叉树的节点数。
  • 空间复杂度:O(min(m, n)),其中 m 和 n 分别是两个二叉树的节点数。空间复杂度取决于递归调用的层数,递归调用的层数不会超过较小的二叉树的最大高度,最坏情况下,二叉树的高度等于节点数。

来源

相同的树 | 力扣(LeetCode)
相同的树 | 题解(LeetCode)


文章标题:相同的树
文章作者:cylong
文章链接:http://www.cylong.com/blog/2020/08/07/same-tree/
有问题或者建议欢迎在下方评论。欢迎转载、引用,但希望标明出处,感激不尽(●’◡’●)

欢迎关注我的其它发布渠道