题目描述
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
解答
递归判断,还可以更简洁
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
| boolean isSymmetrical(TreeNode pRoot) {
if (pRoot == null) {
return true;
}
if (isSame(pRoot.left, pRoot.right)) {
return judgeSymmetrical(pRoot.left, pRoot.right);
} else {
return false;
}
}
private boolean judgeSymmetrical(TreeNode leftNode, TreeNode rightNode) {
if (leftNode == null && rightNode == null) {
return true;
} else {
if (isSame(leftNode.left, rightNode.right) && isSame(leftNode.right, rightNode.left)) {
return judgeSymmetrical(leftNode.left, rightNode.right) && judgeSymmetrical(leftNode.right, rightNode.left);
} else {
return false;
}
}
}
private boolean isSame(TreeNode node1, TreeNode node2) {
if (node1 == null && node2 == null) {
return true;
} else if (node1 != null && node2 != null) {
if (node1.val == node2.val) {
return true;
}
}
return false;
}
|
官方题解
链接：https://www.nowcoder.com/questionTerminal/ff05d44dfdb04e1d83bdbdab320efbcb?answerType=1&f=discussion
来源：牛客网
方法：递归
如图
根据上图可知：若满足对称二叉树，必须满足：
1
2
3
| 1. L->val == R->val
2. L->left->val == R->right->val
3. L->right->val == R->left->val
|
因此可以自顶向下，递归求解即可。
- 设置一个递归函数
isSame(r1, r2),表示如果对称，返回true，否则返回false
- 递归终止条件：
r1==nullptr && r2==nulllptr, 直接返回true，否则，如果只有一个为nullptr，返回false
- 下一步递归：如果
r1->val == r2->val, 则isSame(root1->left, root2->right) && isSame(root1->right, root2->left);
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
bool isSame(TreeNode *root1, TreeNode *root2) {
if (!root1 && !root2) return true;
if (!root1 || !root2) return false;
return root1->val == root2->val &&
isSame(root1->left, root2->right) &&
isSame(root1->right, root2->left);
}
bool isSymmetrical(TreeNode* pRoot)
{
return isSame(pRoot, pRoot);
}
};
|
时间复杂度：O(N)
空间复杂度：O(N),最坏情况下，二叉树退化为链表