代码挑战：在Swift中遍历数据结构

---

最近，我有机会帮助iOS面试计划的学生为大多数人认可的公司准备了一次重要的技术面试。 总体而言， 我的课程融合了代码挑战和实时白板会话的组合，测试了人们在Swift中实现语法，设计模式和算法的能力。

挑战

有时，我会听到人们回覆他们的采访经历。 有时，某些类型的问题会使开发人员感到惊讶。 如果您意识到了挑战，那就太好了！ 对于我们其他人，这里是摘要：

  //给出以下树： 
  // 1 
  // 2 3 
  // 4 5 7 
  // 8 9 


  //由此类实现： 
 类  基站    { 

  var键：T？ 
 左变数：  基站   ？ 
 右：  基站   ？ 
  var高度：  整数 

 在里面（） { 
 自。  高度   = -1 
  } 
  } 

  //使用以下函数获取以下输出： 
  //预期输出： 
  // 1 
  // 2 3 
  // 4 5 7 
  // 8 9 

  //结果：1 2 3 4 5 7 8 9 

分析

关于挑战的有趣之处在于它衡量的事物数量。 这包括一个人的一般技术背景，对Swift的理解以及计算机科学原理。 作为新手或经验丰富的iOS开发人员，我们习惯于使用本机Swift类型（例如Array’s＆Dictionaries）。 这样，很容易遍历这些元素列表。 我们可以使用快速枚举在线性时间内遍历一个数组— O（n）：

 让序列 ：  数组    = [1、2、3、4、5、6、7] 

  //线性时间-O（n） 
 功能   linearSearch（用于值：Int，列表：  数组   ）->  布尔   { 

  //遍历值的范围 
 对于  数  在  清单{ 
 如果数字==值{ 
 返回  真正 
  } 
  } 

 返回  假 
  } 

对于我们的挑战，困难在于基于树的结构不是一维的。 结果，无法应用快速枚举技术。 为了解决这个问题，我们需要提出一种替代方法来考虑根节点以下的值（例如1）。 这个想法可以认为是树的深度 。 考虑以下更详细的视图：

实施

为了满足我们的标准，我们可以应用广度优先搜索（BFS）技术。 与涉及计数，排序或字符串处理的典型面试问题不同，BFS具有特定的目的，否则很难复制。 关于遍历，优点是BFS基于发现。 当遍历复杂的开放式系统（如图形和树）时，此过程可提高灵活性。 考虑以下：

  //宽度优先搜索-遍历树 

 功能   BFSTraverse （）->（）{ 

  //建立队列 
 让bsQueue = Queue <  基站   （） 

  //排队起始节点 
  bsQueue.enQueue（  自   ） 

 而   ！bsQueue.isEmpty（）{ 

  //遍历下一个排队的节点 
 守护  让bitem = bsQueue.deQueue（）  其他   { 
  打破 
  } 

 打印   （“现在遍历的项目：\（bitem.key！）”） 

  //将后代添加到队列 
 如果  让左= bitem.left { 
  bsQueue。  排队   （剩下） 
  } 

 如果  让权利= bitem.right { 
  bsQueue。  排队   （对） 
  } 


  } //结束 

 打印   （bfs遍历完成。”） 

  } 

如上所示，该代码是通过使用队列来实现的。 使用队列安排项目是理想的选择，因为它可以确保以先进先出的方式遍历对象。 正是这个过程使我们能够按顺序打印挑战中的元素。 同样，由于模型基于发现，因此算法将继续搜索新项目，直到队列为空。 在此示例中，BFS算法使用自定义队列。 但是，可以通过使用数组来实现类似的排队功能。

---

喜欢这篇文章吗？ 阅读并发现有关 Medium的 Swift算法书 。