题解 | #对称的二叉树#

实际要比较的是左右子树是否可以翻转。

1. 同时遍历左右子树
2. 采用先序遍历，左子树是中左右，右子树是中右左
3. 比较是否相等，相等则继续遍历，不等则返回false
4. 判断终止条件

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return bool布尔型
     */
    bool isSymmetrical(TreeNode* pRoot) {
        // write code here
        if(pRoot == nullptr) return true;
        return compare(pRoot->left, pRoot->right);
    }

private:
    bool compare(TreeNode* left,TreeNode* right)
    {
        //终止条件
        if(left == nullptr && right == nullptr) return true;
        else if (left == nullptr && right != nullptr) return false;
        else if (left != nullptr && right == nullptr) return false;
        //left ！= right终止返回
        else if (left->val != right->val) return false;

        //此时是左右节点不为空，且相等的情况
        //递推公式
        bool flag1 = compare(left->left, right->right);
        bool flag2 = compare(left->right, right->left);
        //本级函数
        return flag1 && flag2;
    }

};