【刷题日记】二叉树-对称二叉树-L101-Easy
给你一个二叉树的根节点 root ，检查它是否轴对称。（关于根节点轴对称）
思路
- 思路 1
- 利用 L226 的翻转二叉树，将根节点的左子树翻转后与右子树一一比较节点，如果一样，则是关于根节点轴对称。根节点为空则不是轴对称。
- 思路 2
- 不需要考虑翻转，直接一个遍历左边，一个遍历右边，然后比较是否相等。
学习点
代码
思路 1：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| class Solution {
public:
bool compareTree(TreeNode *tree1, TreeNode *tree2)
{
if (!tree1 && !tree2)
return true;
if (!tree1 || !tree2)
return false;
if (tree1->val != tree2->val)
return false;
return (compareTree(tree1->left, tree2->left)
&& compareTree(tree1->right, tree2->right));
}
TreeNode *invertTree(TreeNode *root)
{
if (!root)
return root;
invertTree(root->left);
invertTree(root->right);
TreeNode *tmp_node = root->left;
root->left = root->right;
root->right = tmp_node;
return root;
}
bool isSymmetric(TreeNode* root) {
if (!root)
return false;
TreeNode *invertLeft = invertTree(root->left);
bool res = compareTree(invertLeft, root->right);
return res;
}
};
|
思路 2：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
bool compareTree(TreeNode *tree1, TreeNode *tree2)
{
if (!tree1 && !tree2)
return true;
if (!tree1 || !tree2)
return false;
if (tree1->val != tree2->val)
return false;
return (compareTree(tree1->left, tree2->right)
&& compareTree(tree1->right, tree2->left));
}
bool isSymmetric(TreeNode* root) {
if (!root)
return false;
return compareTree(root->left, root->right);
}
};
|
