专栏首页韦弦的偶尔分享Swift 对称二叉树 - LeetCode

Swift 对称二叉树 - LeetCode

LeetCode

题目: 对称二叉树

给定一个二叉树,检查它是否是镜像对称的。

例如,二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

   1
   / \
  2   2
   \   \
   3    3
说明:

如果你可以运用递归和迭代两种方法解决这个问题,会很加分。

方案一:递归

如果一个树的左子树与右子树镜像对称,那么这个树是对称的。

对称

因此,该问题可以转化为:两个树在什么情况下互为镜像?

如果同时满足下面的条件,两个树互为镜像:

  1. 它们的两个根结点具有相同的值。
  2. 每个树的右子树都与另一个树的左子树镜像对称。

镜像对称

就像人站在镜子前审视自己那样。镜中的反射与现实中的人具有相同的头部,但反射的右臂对应于人的左臂,反之亦然。

上面的解释可以很自然地转换为一个递归函数,如下所示:

代码一:
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
class Solution {
    func isSymmetric(_ root: TreeNode?) -> Bool {
        if (root == nil) {return true}
        return compereRoot(root?.left, root?.right)
    }
    
    func compereRoot(_ leftRoot: TreeNode?, _ rightRoot: TreeNode?) -> Bool {
        if (leftRoot == nil){
            return (rightRoot == nil)
        }
        guard rightRoot != nil else {
            return false
        }
        guard (leftRoot?.val == rightRoot?.val) else {
            return false
        }
        return compereRoot(leftRoot?.left, rightRoot?.right) && compereRoot(leftRoot?.right, rightRoot?.left)
    }
}
复杂度分析
  • 时间复杂度:O(n)。因为我们遍历整个输入树一次,所以总的运行时间为 O(n),其中 n 是树中结点的总数。
  • 空间复杂度:递归调用的次数受树的高度限制。在最糟糕的情况下,树是线性的,其高度为 O(n)。因此,在最糟糕的情况下,由栈上的递归调用造成的空间复杂度为 O(n)
方案二:迭代

除了递归的方法外,我们也可以利用队列进行迭代。队列中每两个连续的结点应该是相等的,而且它们的子树互为镜像。最初,队列中包含的是 root.left 以及 root.right。该算法的工作原理类似于 BFS,但存在一些关键差异。每次提取两个结点并比较它们的值。然后,将两个结点的左右子结点按相反的顺序插入队列中。当队列为空时,或者我们检测到树不对称(即从队列中取出两个不相等的连续结点)时,该算法结束。

代码二:
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
class Solution {
    func isSymmetric(_ root: TreeNode?) -> Bool {
        if (root == nil) {return true}
        var q = [TreeNode?]()
        q.append(root?.left)
        q.append(root?.right)
        
        while !q.isEmpty {
            let t1 = q.popLast()!
            let t2 = q.popLast()!
            //记得添加这个判断、、、不然变成死循环了
            if (t1 == nil && t2 == nil) {
                continue
            }
            if (t1?.val != t2?.val) {
                return false
            }
            q.append(t1?.left)
            q.append(t2?.right)
            q.append(t1?.right)
            q.append(t2?.left)
        }
        return true
    }
}
复杂度分析

时间复杂度:O(n)。因为我们遍历整个输入树一次,所以总的运行时间为 O(n),其中 n 是树中结点的总数。 空间复杂度:搜索队列需要额外的空间。在最糟糕的情况下,我们不得不向队列中插入 O(n) 个结点。因此,空间复杂度为O(n)

用Swift开始学习算法中,在LeetCode中开始做初级算法这一章节,将做的题目在此做个笔记,希望有更好方法同学们cue我哦。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Swift 将有序数组转换为二叉搜索树 - LeetCode

    本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

    韦弦zhy
  • 100 Days of SwiftUI —— Day 12:可选类型

    空(Null)引用——从字面上讲是一个无值的变量——是托尼·霍尔(Tony Hoare)于1965年发明的。回想起来,他说:“我称之为十亿美元的错误(I cal...

    韦弦zhy
  • Swift 合并两个有序链表 - LeetCode

    将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

    韦弦zhy
  • [PHP] 算法-镜像二叉树的PHP实现

    陶士涵
  • Leetcode 100. Same Tree

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • 【Leetcode】100. 相同的树

    大多数的二叉树题目都是用递归可以解的。 所以当拿到二叉树的题目的时候,我们首先就是看看能拆解成哪些子问题。 这个问题的子问题很简单,就是左子树,右子树都相等的二...

    Leetcode名企之路
  • BAT面试题52:判断是否为相同的树?

    大多数的二叉树题目都是用递归可以解的。 所以当拿到二叉树的题目的时候,我们首先就是看看能拆解成哪些子问题。 这个问题的子问题很简单,就是左子树,右子树都相等的二...

    double
  • [剑指offer] 对称的二叉树

    请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。

    尾尾部落
  • 【Leetcode】101. 对称二叉树

    入队顺序依次是, 左子树的左儿子,右子树的右儿子 左子树的右儿子,右子树左右儿子。 这样出队的时候两两检查是不是对称。

    Leetcode名企之路
  • 巨人网络3面面经(游戏开发工程师)

    1面技术面: 1. 首先是自我介绍。 2. 把笔试题翻出来,再考考。 3. tcp连接有多少种状态?怎样查看tcp连接状态? 4. 写一个strcpy函数。 2...

    牛客网

扫码关注云+社区

领取腾讯云代金券