leetcode-107.二叉树的层序遍历 II(OC)

二叉树的层序遍历 II

地址:https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]

示例 2：
输入：root = [1]
输出：[[1]]

示例 3：
输入：root = []
输出：[]

提示：
树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

使用OC 我们需要创建一个BinaryTreeNode节点model 里面的对象如下

/**
 *  值
 */
@property (nonatomic, assign) NSInteger value;
/**
 *  左节点
 */
@property (nonatomic, strong) BinaryTreeNode *leftNode;
/**
 *  右节点
 */
@property (nonatomic, strong) BinaryTreeNode *rightNode;

迭代

迭代方法就是使用层序遍历 一共有多少层 然后将每层的数据保存在一个数组中
count表示每层的数量 开始时为1 也就是根节点，每次数组减少时 count都减少
当count为0时，即为一层遍历完 则将levelArray加入数组的第0个(需求是从下到上)
干代码

- (NSArray *)levelOrderBottom:(BinaryTreeNode *)root
{
    if (root == nil) {
        return @[];
    }
 
    NSMutableArray *dataArray = [NSMutableArray array];
    
    [dataArray addObject:root];
    
    NSInteger count = dataArray.count;
    
    NSMutableArray *levelArray = [NSMutableArray array];
    
    NSMutableArray *numbers = [NSMutableArray array];
    
    while (dataArray.count > 0) {
       
        BinaryTreeNode *node = [dataArray firstObject];
        [dataArray removeObjectAtIndex:0];
        [levelArray addObject:@(node.value)];
        count--;
        
        if (node.leftNode) {
            [dataArray addObject:node.leftNode];
        }
        
        if (node.rightNode) {
            [dataArray addObject:node.rightNode];
        }
        
        if (count == 0) {
            count = dataArray.count;
            
            [numbers insertObject:levelArray atIndex:0];
            levelArray = [NSMutableArray array];
        }
    }
    
    return numbers;
}

验证

{
        BinaryTreeNode *node1 = [[BinaryTreeNode alloc] init];
        node1.value = 3;
        
        BinaryTreeNode *node2 = [[BinaryTreeNode alloc] init];
        node2.value = 9;
        
        BinaryTreeNode *node3 = [[BinaryTreeNode alloc] init];
        node3.value = 20;
        
        node1.leftNode = node2;
        node1.rightNode = node3;

        BinaryTreeNode *node4 = [[BinaryTreeNode alloc] init];
        node4.value = 15;
        
        BinaryTreeNode *node5 = [[BinaryTreeNode alloc] init];
        node5.value = 7;
        
        node3.leftNode = node4;
        node3.rightNode = node5;
        
        NSArray *numbers = [self levelOrderBottom:node1];
        NSLog(@"numbers is %@",numbers);
    }
    
    {
        BinaryTreeNode *node1 = [[BinaryTreeNode alloc] init];
        node1.value = 1;
        
        NSArray *numbers = [self levelOrderBottom:node1];
        NSLog(@"numbers is %@",numbers);
    }
    
    
    {
        NSArray *numbers = [self levelOrderBottom:nil];
        NSLog(@"numbers is %@",numbers);
    }

这个题和102差不多，只是一个是从上到下 一个是从下到上