本文为剑指 offer 系列第五十五篇。
主要知识点为二叉树，就是简单的判断一棵树是不是对称二叉树。
请实现一个函数，用来判断一颗二叉树是不是对称的。
注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
解题思路
什么时候一棵树是对称的呢？
首先，根节点相同；
其次，如果左右子树都不存在，肯定是对称的；如果左右子树只存在一个，那么肯定是不对称的。
如果左右子树都存在，那么左子树是对称的，右子树也是对称的。
最后，通过辅助函数，递归调用，问题就可以得到解决。
解题代码
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
| /*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
bool isSymmetrical(TreeNode* root)
{
if(!root) return true;
return helper(root,root);
}
bool helper(TreeNode* root1,TreeNode* root2){
if(!root1 && !root2) return true;
if(!root1 || !root2) return false;
if(root1->val != root2->val) {
return false;
}else{
return helper(root1->left,root2->right) && helper(root1->right,root2->left);
}
}
};
|
时间复杂度为O(n),空间复杂度为O(n)
以上，本题结束！