目录

对称二叉树

Jimi 收录于 Leetcode Binary Tree

2024-02-11 约 234 字预计阅读 1 分钟

目录

对称二叉树

对称二叉树

方法一：递归

在计算当前二叉树的最大深度时，可以先递归计算出其左子树和右子树的最大深度，然后在 O(1) 时间内计算出当前二叉树的最大深度。递归在访问到空节点时退出。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


func isSymmetric(root *TreeNode) bool {
    return check(root, root)
}

func check(p, q *TreeNode) bool {
    if p == nil && q == nil {
        return true
    }
    if p == nil || q == nil {
        return false
    }
    return p.Val == q.Val && check(p.Left, q.Right) && check(p.Right, q.Left)
}

复杂度分析

时间复杂度：这里遍历了这棵树，渐进时间复杂度为 O(n)。

空间复杂度：这里的空间复杂度和递归使用的栈空间有关，这里递归层数不超过 n，故渐进空间复杂度为 O(n)。