题目描述

给定一个二叉树，检查它是否是镜像对称的。

样例

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3

算法1

时间复杂度 递归O(n)

递归判断两个子树是否互为镜像
两个子树互为镜像当且仅当：
1. 两个子树根节点值相同
2. 第一个子树的左子树和第二个子树的右子树互为镜像，且第一棵子树的右子树和第二棵左子树互为镜像；

时间复杂度分析：从上到下每个节点仅被遍历一遍，所以时间复杂度为O(n)。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int dfs(struct TreeNode* left, struct TreeNode* right) 
{
    if (!left && !right) return true;
    if (!left || !right) return false;
    if (left->val == right->val) {
        return dfs(left->left, right->right) && dfs(left->right, right->left);
    }
    return false;
}

bool isSymmetric(struct TreeNode* root){
    if (!root) {
        return true;
    }

    return dfs(root->left, root->right);
}