美文网首页
iOS 面试题(12):按层遍历二叉树的节点

iOS 面试题(12):按层遍历二叉树的节点

作者: 简_爱SimpleLove | 来源:发表于2017-02-21 10:45 被阅读149次

    注:本文摘自唐巧博客,方便以后查阅。请谅解


    大家都开始上班了吧?我春节在家准备了 5 篇面试题系列的文章,想着大家过节估计也没兴趣阅读,所以节后再发。这些题目大都选自 LeetCode,属于简单到中等类型的难度。还在纠结学算法有没有用的同学,请参阅:搞 iOS 的学算法有意义吗?

    解题代码都是使用 Swift 完成的,我也尽量在代码中使用了 Swift 语言的一些特性,大家可以顺便学学 Swift。

    Have fun!

    问题

    给你一棵二叉树,请按层输出其的节点值,即:按从上到下,从左到右的顺序。

    例如,如果给你如下一棵二叉树:

    输出结果应该是:

    代码模版

    本题的 Swift 代码模版如下:

    解答

    本题出自 LeetCode第 102 题,是一个典型的有关遍历的题目。为了按层遍历,我们需要使用「队列」,来将每一层的节点先保存下来,然后再依次处理。

    因为我们不但需要按层来遍历,还需要按层来输出结果,所以我在代码中使用了两个队列,分别名为level和nextLevel,用于保存不同层的节点。

    最终,整个算法逻辑是:

    1、判断输入参数是否是为空。

    2、将根节点加入到队列level中。

    3、如果level不为空,则:

          3.1 将level加入到结果ans中。

         3.2 遍历level的左子节点和右子节点,将其加入到nextLevel中。

         3.3 将nextLevel赋值给level,重复第 3 步的判断。

    4、将ans中的节点换成节点的值,返回结果。

    因为我们是用 Swift 来实现代码,所以我使用了一些 Swift 语言的特性。例如:队列中我们保存的是节点的数据结构,但是最终输出的时候,我们需要输出的是值,在代码中,我使用了 Swift 的函数式的链式调用,将嵌套数组中的元素类型做了一次变换,如下所示:

    另外,我们也使用了 Swift 特有的guard关键字,来处理参数的特殊情况。

    完整的参考代码如下:

    微信中排版代码非常不便,所以上述代码也可以从我的 Gist 中找到:https://gist.github.com/tangqiaoboy/a7d24ac5ca266d650aaa91615f39ffae

    完成这道题的同学,可以试着练习一下 LeetCode 的第 107 题,看看能不能只改动一行代码,就把 107 题也解决掉。

    欢迎大家把自己的代码也放到 gist 上回复给我,Objective-C 或 Swift 的都行。

    玩得开心

    相关文章

      网友评论

          本文标题:iOS 面试题(12):按层遍历二叉树的节点

          本文链接:https://www.haomeiwen.com/subject/vpbywttx.html