101 Symmetric Tree

101. Symmetric Tree

1. Question

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree[1,2,2,3,4,4,3]is symmetric:
1
1
2
/ \
3
2 2
4
/ \ / \
5
3 4 4 3
Copied!
But the following[1,2,2,null,3,null,3]is not:
1
1
2
/ \
3
2 2
4
\ \
5
3 3
Copied!
Note: Bonus points if you could solve it both recursively and iteratively.

2. Implementation

(1) DFS recursion
1
class Solution {
2
public boolean isSymmetric(TreeNode root) {
3
return isSymmetric(root, root);
4
}
5
6
public boolean isSymmetric(TreeNode node1, TreeNode node2) {
7
if (node1 == null && node2 == null) return true;
8
if (node1 == null || node2 == null) return false;
9
return node1.val == node2.val && isSymmetric(node1.left, node2.right) && isSymmetric(node1.right, node2.left);
10
}
11
}
Copied!
(2) BFS iteration
1
class Solution {
2
public boolean isSymmetric(TreeNode root) {
3
if (root == null) {
4
return true;
5
}
6
7
Queue<TreeNode> queue = new LinkedList<>();
8
queue.add(root);
9
queue.add(root);
10
11
while (!queue.isEmpty()) {
12
TreeNode node1 = queue.remove();
13
TreeNode node2 = queue.remove();
14
15
if (node1 == null && node2 == null) {
16
continue;
17
}
18
else if (node1 == null || node2 == null || node1.val != node2.val) {
19
return false;
20
}
21
22
queue.add(node1.left);
23
queue.add(node2.right);
24
queue.add(node1.right);
25
queue.add(node2.left);
26
}
27
return true;
28
}
29
}
Copied!

3. Time & Space Complexity

DFS recursion: 时间复杂度: O(n), 空间复杂度: O(n)
BFS iteration: 时间复杂度: O(n), 空间复杂度: O(n)