5 月 11 日 每日一题
101. Symmetric Tree
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
1
2
| Input: root = [1,2,2,3,4,4,3]
Output: true
|
思路
Recursive 写法：
首先思考问题与子问题的递归关系，可分为三种 case，第一种是只有一个 node，必然 true；第二种是三个 node，需要满足 left->val == right->val；第三种是 height 大于 3 的 completed tree，需要满足 left->val == right->val 并且 left->left tree 与 right->right tree 相同，left->right 与 right->left 相同。
之后思考 base case，left/right 有一个空或全空。
最后将以上归纳为函数代码(首先将 root->left，right）传入函数可以自然判断前两种 case。
Iterative 写法：
逻辑类似 BSF，首先将 root->left,right 放入 queue，while 判断条件为 queue 非空，在 while 内判断 val 并且按递归 case3 的顺序 push 进 queue.
代码
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
| class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(!root)
return true;
return SymmetricHelper(root->left, root->right);
}
bool SymmetricHelper(TreeNode *left, TreeNode *right){
if(!left || !right)
return left == right;
if(left->val != right->val)
return false;
return SymmetricHelper(left->left, right->right) && SymmetricHelper(left->right, right->left);
}
};
bool isSymmetric(TreeNode* root) {
if(!root) return true;
queue<TreeNode*> queue;
queue.push(root->left);
queue.push(root->right);
while(!queue.empty()) {
TreeNode *left = queue.front(); queue.pop();
TreeNode *right = queue.front(); queue.pop();
if(!left || !right) return left == right;
if(left->val != right->val) return false;
queue.push(left->left);
queue.push(right->right);
queue.push(left->right);
queue.push(right->left);
}
return true;
}
|