source: https://leetcode.com/problems/symmetric-tree
C/C++ Solution to LeetCode problem 101. Symmetric Tree.
Problem
Given the root
of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
Examples
Example 1:
Input: root = [1,2,2,3,4,4,3]
Output: true
Example 2:
Input: root = [1,2,2,null,3,null,3]
Output: false
Constraints
- The number of nodes in the tree is in the range
[1, 1000].
-100 <= Node.val <= 100
Follow up: Could you solve it both recursively and iteratively?
Solution
- We have two parts for every node (left and right), we need to check if left == right. Will use 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 but their values are different, return
false
.- Insert to the queue two pairs
left and right
andright and left
- Pop the first element (pair of nodes) from the queue.
- Return
true
.
- Return
- If one node exists, but the other no, return
- A Depth First Search solution.
Solution 1:
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
/**
* 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 isSymmetric(TreeNode* root) {
queue<pair<TreeNode *, TreeNode *>> bfs;
bfs.push({root->left, root->right});
TreeNode *a;
TreeNode *b;
while (!bfs.empty()) {
a = bfs.front().first;
b = bfs.front().second;
if (!a != !b)
return false;
if (a && b) {
if (a->val != b->val)
return false;
bfs.push({a->left, b->right});
bfs.push({a->right, b->left});
}
bfs.pop();
}
return true;
}
};
Solution 2:
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
/**
* 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 {
private:
bool exploreNode(TreeNode* nodeL, TreeNode* nodeR) {
if (!nodeL != !nodeR)
return false;
if (!nodeL && !nodeR)
return true;
bool a = exploreNode(nodeL->left, nodeR->right);
bool b = exploreNode(nodeL->right, nodeR->left);
if (!a || !b)
return false;
return nodeL->val == nodeR->val;
}
public:
bool isSymmetric(TreeNode* root) {
return exploreNode(root->left, root->right);
}
};