Coding Spirit

一位程序员,比较帅的那种

0%

Algorithm Puzzles: Symmetric Tree

Algorithm Puzzles everyday every week sometimes: Symmetric Tree

Puzzle

Puzzle from leetcode:

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
2
3
4
5
    1
/ \
2 2
/ \ / \
3 4 4 3

But the following [1,2,2,null,3,null,3] is not:

1
2
3
4
5
  1
/ \
2 2
\ \
3 3

Solving

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
bool isSymmetric(const TreeNode* const root) {
if (root != nullptr) {
return isSubTreeSymmetric(root->left, root->right);
}

return true;
}

private:
bool isSubTreeSymmetric(const TreeNode* const r, const TreeNode* const l) {
if (r == l) {
return true;
}

if (r == nullptr || l == nullptr) {
return false;
}

return (r->val == l->val) && isSubTreeSymmetric(r->right, l->left) &&
isSubTreeSymmetric(r->left, l->right);
}
};