题解 | #对称的二叉树#

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
#include <stack>
#include <vector>
class Solution {
public:

  //开始以为求中序遍历，按回文数那样就可以，后来发现不行，一种遍历不能确定一颗树，也就是有多颗树对应这个遍历    序列，所以特殊的过不了，看了下评论区的大佬的
    // void Inordertraversal(vector<int>&num,TreeNode *pRoot)
    // {
    //     stack<TreeNode*>st;
    //     while(pRoot||!st.empty())
    //     {
    //         if (pRoot) 
    //         {
    //             st.push(pRoot);
    //             pRoot = pRoot->left;
    //         }
    //         else 
    //         {
    //             pRoot = st.top();
    //             num.push_back(pRoot->val);
    //             st.pop();
    //             pRoot = pRoot->right;
    //         }
    //     }
    // }
    // bool isSymmetrical(TreeNode* pRoot) 
    // {
    //     vector<int> num;
    //     Inordertraversal(num,pRoot);
    //     for(int i=0;i<(num.size()/2);i++)
    //     {

    //         if (num[i] != num[num.size() - i - 1]) 
    //         {
    //             return false;
    //         }
    //     }
    //     return true;
    // }

    //两个指针同时移动
    bool DoublePointer(TreeNode* left,TreeNode* right)
    {
        //同为空，return true
        if (!left&&!right) return true;
        //不同为空，return false
        if (!left||!right) return false;
        //同时不为空，比较值，将对应节点做递归调用
        return left->val == right->val&&
        DoublePointer(left->left,right->right)&&
        DoublePointer(left->right,right->left);
    }
    bool isSymmetrical(TreeNode* pRoot)
    {
        //树空，return true
        if(!pRoot) return true;
        return DoublePointer(pRoot->left,pRoot->right);
    }
};