剑指offer 对称的二叉树（思维）

题目描述

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

解题思路：

正规的解法是传入两个节点，然后判断它们是不是对称的。因为按照对称二叉树的定义，就是需要一层一层判断是否是对称的。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    bool dfs(TreeNode * left,TreeNode * right){
        if((left && !right) || (!left && right))return false;
        if(!left && !right)return true;
        if(left->val != right->val)return false;
        return dfs(left->left,right->right) && dfs(left->right,right->left);
    }
    bool isSymmetrical(TreeNode* pRoot)
    {
        return ! pRoot || dfs(pRoot->left,pRoot->right);
    }

};

第二种做法就是，通过观察，我们可以查看叶子节点是否镜像对称即可。需要用到一点回溯。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    vector<pair<int,int>> mv;
    TreeNode * head;
    int finsuc;
    int suc;
    void check(TreeNode * root,int n){
        if(n == mv.size()){
            suc = 1;
            return;
        }
        if(mv[n].first == 0){
            if(root->right && root->right->val == mv[n].second){
                check(root->right,n+1);
            }
        }else if(root->left && root->left->val == mv[n].second)check(root->left,n+1);
    }
    void dfs(TreeNode * root){
         
        if(root->left){
            mv.push_back({0,root->left->val});
            dfs(root->left);
            mv.pop_back();
        }
        if(root->right){
            mv.push_back({1,root->right->val});
            dfs(root->right);
            mv.pop_back();
        }
        if(root->left == NULL && root->right == NULL){
            suc = 0;
            check(head,0);
            if(!suc)finsuc = 0;
        }
    }
    bool isSymmetrical(TreeNode* pRoot)
    {
        if(!pRoot)return true;
        finsuc = 1;
        head = pRoot;
        dfs(pRoot);
        return finsuc;
    }
 
};