Task
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
Example 1:
1
2
3
4
5
6
7
|
Input: 1 1
/ \ / \
2 3 2 3
[1,2,3], [1,2,3]
Output: true
|
Example 2:
1
2
3
4
5
6
7
|
Input: 1 1
/ \
2 2
[1,2], [1,null,2]
Output: false
|
Example 3:
1
2
3
4
5
6
7
|
Input: 1 1
/ \ / \
2 1 1 2
[1,2,1], [1,1,2]
Output: false
|
Solution
- 递归依次遍历每个节点即可，若两树的对应节点存在值不一样，则false
- 时间复杂度：遍历每个节点，O(n)
- 空间复杂度：递归深度取决于树的深度，O(h)
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
|
// Runtime: 0 ms, faster than 100.00% of C++ online submissions for Same Tree.
// Memory Usage: 10.2 MB, less than 5.57% of C++ online submissions for Same Tree.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
//都为空则相同
if(!p && !q) return true;
//一个空一个非空则不相同
if(!p || !q) return false;
//遍历时发现值不一样，则不相同
if(p->val != q->val) return false;
//遍历左子树和右子树，并求与
return isSameTree(p->left,q->left)
&& isSameTree(p->right,q->right);
}
};
|