LeetCode 101. 对称二叉树
题目描述
思路分析
递归
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 判断两个节点是否镜像对称
func isMirror(left *TreeNode, right *TreeNode) bool {
if left == nil && right == nil {
return true
}
if left == nil || right == nil {
return false
}
if left.Val != right.Val {
return false
}
// 递归判断
return isMirror(left.Left, right.Right) && isMirror(left.Right, right.Left)
}
func isSymmetric(root *TreeNode) bool {
if root == nil {
return true
}
return isMirror(root.Left, root.Right)
}
- 时间复杂度：
O(n)，其中n是树中节点的数量，因为每个节点都需要被访问一次。- 空间复杂度：
O(h)，其中h是树的高度，递归调用栈的空间复杂度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return isMirror(root.left, root.right);
}
public boolean isMirror(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
} else if (left == null || right == null) {
return false;
}
if (left.val != right.val) {
return false;
}
return isMirror(left.left, right.right) && isMirror(left.right, right.left);
}
}
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！