二叉树 – 对称二叉树

对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

解题思路：

• 1 分解思路，后序遍历
• 2 先判断左右子树是否对称，再判断根节点是否对称
• 3 判断对称二叉树的经典步骤
  • 3.1 判断左右孩子为空的情况
  • 3.2 判断左右孩子值不相等的情况
  • 3.3 判断左->左孩子和右->右孩子相等的情况
  • 3.4 判断左->右孩子和右->左孩子相等的情况

class Solution {
public:
    bool compare(TreeNode* left, TreeNode* right){
        // 1 判断空
        if(left != nullptr && right == nullptr) return false;
        else if(left == nullptr && right != nullptr) return false;
        else if (left == nullptr && right == nullptr) return true;
        // 2 判断左右孩子的值是否相等
        else if (left->val != right->val) return false;
        // 3 left->left VS right->right
        int outside = compare(left->left, right->right);
        // 4 left->right VS right->left
        int inside = compare(left->right, right->left);
        int same = outside && inside;
        return same;
    }

    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) return true;
        return compare(root->left, root->right);
    }
};