0%

2020-01-11-SameTree

LeetCode 100

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
Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

Input: 1 1
/ \ / \
2 3 2 3

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

Output: true
Example 2:

Input: 1 1
/ \
2 2

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

Output: false
Example 3:

Input: 1 1
/ \ / \
2 1 1 2

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

Output: false

Solution

题目其实很简单的一个递归Recursion,我们很轻松可以通过递归来解决

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
// p and q are both null
if (p == null && q == null) return true;
// one of p and q is null
if (q == null || p == null) return false;
if (p.val != q.val) return false;
return isSameTree(p.right, q.right) &&
isSameTree(p.left, q.left);
}
}

时间复杂度为O(n),控件复杂度为O(logn)~O(n)之间,这道题就不考虑其他解法了,recursion目前看来是最优解