LeetCode101 Symmetric Tree

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

样例

1
2
3
4
5
6
7
8
9
10
Input:
[1,2,2,3,4,4,3]
1
/ \
2 2
/ \ / \
3 4 4 3

Output:
true
1
2
3
4
5
6
7
8
9
10
Input:
[1,2,2,null,3,null,3]
1
/ \
2 2
\ \
3 3

Output:
false

思路

判断一颗二叉树是否是对称的。

首先判断给定的二叉树是否是空树,空树也算是对称的。

然后判断左右子树是否是对称的。即判断左右子树的值是否相等,并且递归下去判断「左子树的左儿子」和「右子树的右儿子」是否是对称的,以及「左子树的右儿子」和「右子树的左儿子」是否是对称的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
// 判断左右子树是否相等
bool check(TreeNode* l, TreeNode* r) {
// 两棵都是空树
if (!l && !r) return true;
// 有一棵不是空树
if (!l ^ !r) return false;
return l->val == r->val && check(l->left, r->right) && check(l->right, r->left);
}
bool isSymmetric(TreeNode* root) {
if (root == nullptr) return true;
return check(root->left, root->right);
}
};
分享到 评论