asunquan.com

不忘初心 不止于行

职场新人 iOS菜鸟 就职于搜狐畅游 从事iOS/tvOS的SDK开发 对于游戏市场有点点了解 平日和一只小Corgi同吃同睡


[转改]面试题: 按层遍历二叉树的节点(Objective-C版)

题目

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

	3
   /  \   
  9   20
     /  \
    15   7

输出结果应该是:

[
  [3],
  [9, 20],
  [15, 7]  
]

分析及答案

  • 二叉树节点定义

    采用单链表的形式, 只从根节点指向子节点, 不保存父节点

    @interface BinaryTreeNode : NSObject
    
    /**
     该节点的值
     */
    @property (nonatomic, assign) NSInteger value;
    
    /**
     该节点的左节点
     */
    @property (nonatomic, strong) BinaryTreeNode *leftNode;
    
    /**
     该节点的右节点
     */
    @property (nonatomic, strong) BinaryTreeNode *rightNode;
    
    @end
    
  • 本题出自LeetCode第102题, 是一个典型的有关遍历的题目. 为了按层遍历, 我们需要使用队列, 来将每一层的节点先保存下来, 然后再依次处理.

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

    最终,整个算法逻辑是:

    1. 判断输入参数是否是为空。
    2. 将根节点加入到队列queueArray中。
    3. 如果queueArray不为空,则:
    4. 3.1 将queueArray加入到结果 ans 中。
    5. 3.2 遍历queueArray的左子节点和右子节点,将其加入到 nextLevel 中。
    6. 3.3 将 nextLevel 赋值给 level,重复第 3 步的判断。
    7. 将 ans 中的节点换成节点的值,返回结果。
    + (NSArray *)levelorderTraversalTree:(BinaryTreeNode *)rootNode
    {
        if (!rootNode)
        {
            return nil;
        }
          
        NSMutableArray *result = [NSMutableArray array];
        NSMutableArray *queueArray = [NSMutableArray array];
          
        // 插入根节点
        [queueArray addObject:rootNode];
          
        while (queueArray.count)
        {
            BinaryTreeNode *node = queueArray.firstObject;
              
            // 先进先出, 移除节点
            [queueArray removeObjectAtIndex:0];
              
            // 插入左节点
            if (node.leftNode)
            {
                [queueArray addObject:node.leftNode];
            }
              
            // 插入右节点
            if (node.rightNode)
            {
                [queueArray addObject:node.rightNode];
            }
        }
          
        return result;
    }
    
最近的文章

数据结构学习笔记(一)--绪论

[TOC]绪论什么是数据结构一般来说, 用计算机解决一个具体问题时, 大致需要经过下列几个步骤: 首先要从具体问题抽象出一个适当的数学模型, 然后设计一个解此数学模型的算法, 最后编出程序, 进行测试, 调整直至得到最终解答. 需求数学模型的实质是分析问题, 从中提取操作的对象, 并找出这些操作对象之间含有的关系, 然后用数学的语言加以描述.数据结构在计算机科学中是一门综合行的专业基础课, 数据结构的研究不仅涉及到计算机硬件(特别是编码理论, 存储装置和存取方法等)的研究范围, 而且和计算...…

数据结构继续阅读
更早的文章

[转]面试题: 创建一个可以被取消执行的block

题目我们知道block默认是不能被取消掉的, 请你封装一个可以被取消执行的block wrapper类, 定义如下typedef void(^Block)();@interface CancelableObject : NSObject- (id)initWithBlock:(Block)block;- (void)start;- (void)cancel;@end分析及答案 方法一: 创建一个类, 将要执行的block封装起来, 然后类的内部有一个_isCancel变量, 在执...…

iOS开发面试题继续阅读