一开始想中序遍历, 然后左右判断.
但是是不对的. 如果有空节点的话.
于是, 空节点加数.
[1,2,3,3,null,2,null]
还是错. 两个空加两个 0.
0,3,0,2,0,1,0,2,0,3,0
再改: 只有一个空才加.(指针不能异或, 转成 longlong).
[5,4,1,null,1,null,4,2,null,2,null]
还是错. 这个数据很厉害. 我觉得要补成满二叉树才行...... 放弃.
0,4,2,1,0,5,0,1,2,4,0
其实有个更可怕的, 直接只有左子树.
于是开始想递归.
- /**
- * Definition for a binary tree node.
- * struct TreeNode {
- * int val;
- * TreeNode *left;
- * TreeNode *right;
- * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
- * };
- */
- class Solution {
- public:
- bool isSymmetric(TreeNode* root) {
- if(!root){
- return true;
- }
- return soln(root->left,root->right);
- }
- bool soln(TreeNode* left,TreeNode* right){
- if((left==NULL)&&(right==NULL)){
- return true;
- }
- else if(left!=NULL&&right!=NULL){
- if(left->val==right->val){
- bool res=true;
- res=soln(left->left,right->right);
- res=res&&soln(left->right,right->left);
- return res;
- }
- else{
- return false;
- }
- }
- else{
- return false;
- }
- }
- };
- View Code
简化代码:(别人的)
- class Solution {
- public:
- bool isSymmetric(TreeNode* root) {
- return Symmetric(root,root);
- }
- bool Symmetric(TreeNode* root1,TreeNode* root2)
- {
- if(root1==NULL&&root2==NULL)
- return true;
- if(root1==NULL||root2==NULL)
- return false;
- if(root1->val!=root2->val)
- return false;
- return Symmetric(root1->left,root2->right)&&Symmetric(root1->right,root2->left);
- }
- View Code
- (还是别人的)
- class Solution {
- public:
- bool isSymmetric(TreeNode* root) {
- return !root || isSym(root->left, root->right);
- }
- private:
- bool isSym(TreeNode* left, TreeNode* right) {
- return (!left && !right) || (left && right && left->val == right->val && isSym(left->left, right->right) && isSym(left->right, right->left));
- }
- };
两个 return
来源: http://www.bubuko.com/infodetail-2597170.html