Swift 翻转二叉树 invert binary tree in Swift

分享到:  QQ好友和群QQ好友和群 QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友 微信微信
查看查看358 回复回复2 收藏收藏 分享淘帖 转播转播 分享分享 微信
查看: 358|回复: 2
收起左侧

Swift 翻转二叉树 invert binary tree in Swift

[复制链接]
攻城狮 发表于 2016-6-29 16:30:10 | 显示全部楼层 |阅读模式
快来登录
获取优质的苹果资讯内容
收藏热门的iOS等技术干货
拷贝下载Swift Demo源代码
订阅梳理好了的知识点专辑

已经被玩烂的题目,纯粹好玩,直接上代码吧。

Swift 翻转二叉树 invert binary tree in Swift

Swift 翻转二叉树 invert binary tree in Swift - 敏捷大拇指 - Swift 翻转二叉树 invert binary tree in Swift





1、定义树:

[Swift] 纯文本查看 复制代码
class Tree {  
  var key: Int
  var leftTree: Tree?
  var rightTree: Tree?

  init(key: Int) {
    self.key = key
  }
}





2、非递归实现

思路:广度优先。从上往下,从左往右。到达一层,从左到右翻完这一层的节点,再翻下一层。通过数组的方式实现节点的保存。O(n)。

这里一开始我踩了个坑,忘记每次把根节点移除了,切记。


[Swift] 纯文本查看 复制代码
func invertNonRecursive(root: Tree) {  
  var nodes = [Tree]()
  nodes.append(root)
  while !nodes.isEmpty {
    if let node = nodes.first {
      nodes.removeFirst()
      let tempLeftTree = node.leftTree
      node.leftTree = node.rightTree
      node.rightTree = tempLeftTree

      if let leftT = node.leftTree {
        nodes.append(leftT)
      }
      if let rightT = node.rightTree {
        nodes.append(rightT)
      }
    }
  }
}





3、递归实现

思路:深度优先。先翻一次,之后对左右子树递归翻转。O(n)。

[Swift] 纯文本查看 复制代码
func invertBinaryTreeWithRecursive(root: Tree) {  
  let tempTree = root.leftTree
  root.leftTree = root.rightTree
  root.rightTree = tempTree
  if let leftTree = root.leftTree {
    invertBinaryTreeWithRecursive(leftTree)
  }
  if let rightTree = root.rightTree {
    invertBinaryTreeWithRecursive(rightTree)
  }
}





作者:KittenYang

都看到这里了,就把这篇资料推荐给您的好朋友吧,让他们也感受一下。

回帖是一种美德,也是对楼主发帖的尊重和支持。您的赞赏是我前进的方向。

*声明:敏捷大拇指是全球最大的Swift开发者社区、苹果粉丝家园、智能移动门户,所载内容仅限于传递更多最新信息,并不意味赞同其观点或证实其描述;内容仅供参考,并非绝对正确的建议。本站不对上述信息的真实性、合法性、完整性做出保证;转载请注明来源并加上本站链接,敏捷大拇指将保留所有法律权益。如有疑问或建议,邮件至marketing@swifthumb.com

*联系:微信公众平台:“swifthumb” / 腾讯微博:@swifthumb / 新浪微博:@swifthumb / 官方QQ一群:343549891(满) / 官方QQ二群:245285613 ,需要报上用户名才会被同意进群,请先注册敏捷大拇指

评分

参与人数 1金钱 +10 收起 理由
Anewczs + 10 发帖就是光荣,分享精神可嘉!.

查看全部评分

swifter 发表于 2016-6-30 01:19:55 | 显示全部楼层
简单实用!
我是90后 发表于 2016-6-30 03:02:17 | 显示全部楼层
O(n)
不能再简单了~
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

淘帖专辑
我要发帖

分享扩散

都看到这里了,就把这资料推荐给您的好朋友吧,让他们也感受一下。
您的每一位朋友访问此永久链接后,您都将获得相应的金钱积分奖励
热门推荐

合作伙伴

Swift小苹果

  • 北京治世天下科技有限公司
  • ©2014-2016 敏捷大拇指
  • 京ICP备14029482号
  • Powered by Discuz! X3.1 Licensed
  • swifthumb Wechat Code
  •   
快速回复 返回顶部 返回列表