对称的二叉树(剑指Offer-28)

题面

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

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

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

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

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

示例

示例 1：

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

示例 2：

1输入：root = [1,2,2,null,3,null,3]
2输出：false

限制

10 <= 节点个数 <= 1000

思路

递归。

代码

 1/**
 2 * Definition for a binary tree node.
 3 * struct TreeNode {
 4 *     int val;
 5 *     TreeNode *left;
 6 *     TreeNode *right;
 7 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8 * };
 9 */
10class Solution {
11    bool dfs(TreeNode *left, TreeNode *right){
12        if(left==NULL && right==NULL) return true;
13        if(left==NULL || right==NULL || left->val!=right->val) return false;
14        return dfs(left->left, right->right) && dfs(left->right, right->left);
15    }
16public:
17    bool isSymmetric(TreeNode* root) {
18        if(root==NULL) return true;
19        return dfs(root->left, root->right);
20    }
21};