source: https://leetcode.com/problems/same-tree
C/C++ Solution to LeetCode problem 100. Same Tree.
Problem
Given the roots of two binary trees p
and q
, 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.
Examples
Example 1:
Input: p = [1,2,3], q = [1,2,3]
Output: true
Example 2:
Input: p = [1,2], q = [1,null,2]
Output: false
Example 3:
Input: p = [1,2,1], q = [1,1,2]
Output: false
Constraints
- The number of nodes in both trees is in the range
[0, 100]
. -104 <= Node.val <= 104
Solution
We will explore both trees simultaneously with a BFS (Breadth First Search) algorithm.
- Insert the root nodes to the queue using
pair<TreeNode*, TreeNode*>
. - While the queue has nodes:
- If one node exists, but the other no, return
false
. - If both nodes exist:
- If their values are different, return
false
. - Insert to the queue the pointers to the left and right of each node.
- If their values are different, return
- Pop the first element (pair of nodes) from the queue
- If one node exists, but the other no, return
- Return
true
.
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
/**
* 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) {
queue<pair<TreeNode *, TreeNode *>> bfs;
bfs.push({p, q});
TreeNode *a;
TreeNode *b;
while (!bfs.empty()) {
a = bfs.front().first;
b = bfs.front().second;
if ((!a && b) || (a && !b))
return false;
if (a && b) {
if (a->val != b->val)
return false;
bfs.push({a->left, b->left});
bfs.push({a->right, b->right});
}
bfs.pop();
}
return true;
}
};