Swift 算法实战之路:二叉树

[中文教程]
分享到:  QQ好友和群QQ好友和群 QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友 微信微信
查看查看106 回复回复1 收藏收藏1 分享淘帖 转播转播 分享分享 微信
查看: 106|回复: 1
收起左侧

[中文教程] Swift 算法实战之路:二叉树

[复制链接]
代码买卖 发表于 2016-9-7 03:34:13 | 显示全部楼层 |阅读模式
快来登录
获取优质的苹果资讯内容
收藏热门的iOS等技术干货
拷贝下载Swift Demo源代码
订阅梳理好了的知识点专辑
本帖最后由 代码买卖 于 2016-9-7 04:43 编辑


之前我们探索了数组、字典、字符串链表栈、队列的处理和应用。今天我们来讲讲平常相对很少用到,面试中却是老面孔的数据结构:二叉树。本期的内容有:

  • 基本概念:实现,深度 ,二叉查找树
  • 遍历
  • 苹果面试题:在iOS中展示二叉树


Swift 算法实战之路:二叉树 0

Swift 算法实战之路:二叉树 - 敏捷大拇指 - Swift 算法实战之路:二叉树 0





1、概念

Swift 算法实战之路:二叉树 1

Swift 算法实战之路:二叉树 - 敏捷大拇指 - Swift 算法实战之路:二叉树 1


首先介绍下二叉树。二叉树中每个节点最多有两个子节点,一般称为左子节点和右子节点,并且二叉树的子树有左右之分,其次序不能任意颠倒。下面是节点的Swift实现:

[Swift] 纯文本查看 复制代码
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
  }
}


一般在面试中,会给定二叉树的根节点。要访问任何其他节点,只要从起始节点开始往左/右走即可。

在树中,节点的层次从根开始定义,根为第一层,树中节点的最大层次为树的深度

[Swift] 纯文本查看 复制代码
// 计算树的最大深度
func maxDepth(root: TreeNode?) -> Int {
  guard let root = root else {
    return 0
  }
  return max(maxDepth(root.left), maxDepth(root.right)) + 1
}


面试中,最常见的是二叉查找树,它是一种特殊的二叉树。它的特点就是左子树中节点的值都小于根节点的值,右子树中节点的值都大于根节点的值。那么问题来了,给你一棵二叉树,怎么判断它是二叉查找树?我们根据定义,可以写出以下解法:

[Swift] 纯文本查看 复制代码
// 判断一颗二叉树是否为二叉查找树
func isValidBST(root: TreeNode?) -> Bool {
  return _helper(root, nil, nil)
}

private func _helper(node: TreeNode?, _ min: Int?, _ max: Int?) -> Bool {
  guard let node = node else {
    return true
  }
  // 所有右子节点都必须大于根节点
  if min != nil && node.val <= min {
    return false
  }
  // 所有左子节点都必须小于根节点
  if max != nil && node.val >= max {
    return false
  }

  return _helper(node.left, min, node.val) && _helper(node.right, node.val, max)
}


上面的代码有这几个点指点注意:

  • 二叉树本身是由递归定义的,所以原理上所有二叉树的题目都可以用递归来解
  • 二叉树这类题目很容易就会牵涉到往左往右走,所以写helper函数要想到有两个相对应的参数
  • 记得处理节点为nil的情况,尤其要注意根节点为nil的情况





2、遍历

最常见的树的遍历有三种,前序、中序、后序遍历。这三种写法相似,无非是递归的顺序略有不同。面试时候有可能考察的是用非递归的方法写这三种遍历:用栈实现。

[Swift] 纯文本查看 复制代码
// 用栈实现的前序遍历
func preorderTraversal(root: TreeNode?) -> [Int] {
  var res = [Int]()
  var stack = [TreeNode]()
  var node = root

  while !stack.isEmpty || node != nil {
    if node != nil {
      res.append(node!.val)
      stack.append(node!)
      node = node!.left
    } else {
        node = stack.removeLast().right
    }
  }

  return res
}


除了这三种最常见的遍历之外,还有一种遍历是层级遍历(广度优先遍历),请看下图:

Swift 算法实战之路:二叉树 2

Swift 算法实战之路:二叉树 - 敏捷大拇指 - Swift 算法实战之路:二叉树 2


这棵树的层级遍历结果为[[1], [2, 3], [4, 5, 6, 7], [8, 9, 10, 11, 12, 13, 14, 15]]。

层级遍历相比于以上三种常见遍历的好处在于:如果构建一棵树,那么至少要知道中序遍历和前序/后序遍历中的一种,也就是至少要知道两种遍历方式;但是层级遍历自己便可以唯一确定一棵树。我们来看下面一道苹果公司的面试题。




3、实战

Given a binary tree, please design an iOS app to demo it.


首先一个简单的app是mvc架构,所以我们就要想,在View的层面上表示一棵二叉树?我们脑海中浮现树的结构是这样的:

Swift 算法实战之路:二叉树 3

Swift 算法实战之路:二叉树 - 敏捷大拇指 - Swift 算法实战之路:二叉树 3

理想中的树长这样

所以是不是在View的界面上,每个节点弄个UILabel来表示,然后用数学方法计算每个UIlabel对应的位置,从而完美的显示上图的样子?

这个想法比较简单粗暴,是最容易想到,实现之后又是最直观展示一棵二叉树的,但是它有以下两个问题:

  • 每个UILabel的位置计算起来比较麻烦;
  • 如果一棵树有很多节点(比如1000个),那么当前界面就会显示不下了,这时候咋办?就算用UIScrollView来处理,整个树也会变得非常不直观,每个节点所对应的UILabel位置计算起来就会更费力。


要处理大量数据,我们就想到了UITableView。假如每一个cell对应一个节点,以及其左、右节点,那么我们就可以清晰的展示一棵树。比如上图这棵树,用UITableView就可以写成这样:

Swift 算法实战之路:二叉树 4

Swift 算法实战之路:二叉树 - 敏捷大拇指 - Swift 算法实战之路:二叉树 4

用UITableView表现一棵树

其中"#"表示空节点。明眼人可以看出,我们是按照层级遍历的方式布局整个UITableView。这种做法解决了上面两个问题:

  • 无需进行位置计算,UITableView提供复用Cell,效率大幅提高
  • 面对很多节点的问题,可以先处理一部分数据,然后用处理infinite scroll的方式来加载剩余数据


接着问题来了,给你一棵二叉树,如何得到它的层级遍历?其实层级遍历就是图的广度优先遍历,而广度优先遍历很自然就会用到队列,所以我们不妨用队列来帮助实现树的层级遍历:

[Swift] 纯文本查看 复制代码
func levelOrder(root: TreeNode?) -> [[Int]] {
  var res = [[Int]]()
  // 用数组来实现队列
  var queue = [TreeNode]()

  if let root = root {
    queue.append(root)
  }

  while queue.count > 0 {
    var size = queue.count
    var level = [Int]()

    for _ in 1...size {
      let node = queue[0]
      queue.removeAtIndex(0)

      level.append(node.val)
      if let left = node.left {
        queue.append(left)
      }
      if let right = node.right {
        queue.append(right)
      }
    }
    res.append(level)
  }

  return res
}





4、总结

到这里为止,我们已经把重要的数据结构都分析了一遍。要知道,这些数据结构都不是单独存在的,我们在解决二叉树的问题时,用到了队列;解决数组的问题,也会用到字典或是栈。在真正面试或是日常Coding中,最低的时间复杂度是首要考虑,接着是优化空间复杂度,其次千万不要忘记考虑特殊情况。在Swift中,用let和var的地方要区分清楚,该不该定义数据为optional,有没有处理nil的情况都是很容易忽略的,希望大家多多练习,融会贯通。

下次我们介绍Swift排序




相关内容

Swift 算法实战之路:基本语法与技巧

Swift 算法实战之路:数组,字符串,集合,与字典

Swift 算法实战之路:链表

Swift 算法实战之路:栈和队列

Swift 算法实战之路:二叉树

Swift 算法实战之路:排序

Swift 算法实战之路:二分搜索

Swift 算法实战之路:深度和广度优先搜索

Swift 算法实战之路:动态规划




作者:故胤道长

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

回帖是一种美德,也是对楼主发帖的尊重和支持。

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

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

嗯,不错!期待更多好内容,支持一把:
支持敏捷大拇指,用支付宝支付10.24元 支持敏捷大拇指,用微信支付10.24元

评分

参与人数 1金钱 +10 贡献 +10 专家分 +10 收起 理由
Anewczs + 10 + 10 + 10 32个赞!专家给力!

查看全部评分

本帖被以下淘专辑推荐:

电音之王 发表于 2016-9-10 22:58:44 | 显示全部楼层
经典的二叉树
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

做任务,领红包。
我要发帖

分享扩散

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

合作伙伴

Swift小苹果

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