leetcode-589. N叉树的前序遍历(OC)

N叉树的前序遍历

地址:https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal/

 给定一个 n 叉树的根节点  root ，返回 其节点值的 前序遍历 。

 n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。


 示例 1：
 输入：root = [1,null,3,2,4,null,5,6]
 输出：[1,3,5,6,2,4]
 
 
 示例 2：
 输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
 输出：[1,2,3,6,7,11,14,4,8,12,5,9,13,10]
  

 提示：

 节点总数在范围 [0, 104]内
 0 <= Node.val <= 104
 n 叉树的高度小于或等于 1000
  

 进阶：递归法很简单，你可以使用迭代法完成此题吗?

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

/**
 *  值
 */
@property (nonatomic, assign) NSInteger value;

/**
 * N节点
 */
@property (nonatomic, strong) NSArray <BinaryTreeNode *> *dataArray;

递归

很简单 上代码吧

- (NSArray *)preorder1:(BinaryTreeNode *)root
{
    if (root == nil) {
        return @[];
    }
    
    NSMutableArray *values = [NSMutableArray array];
    
    [values addObject:@(root.value)];
    
    for (BinaryTreeNode *node in root.dataArray) {
        
        NSArray *dataArray = [self preorder1:node];
        
        [values addObjectsFromArray:dataArray];
    }
    
    return values;
}

迭代

- (NSArray *)preorder2:(BinaryTreeNode *)root
{
    if (root == nil) {
        return @[];
    }
    
    NSMutableArray *values = [NSMutableArray array];

    NSMutableArray *dataArray = [NSMutableArray array];
    [dataArray addObject:root];
    
    while (dataArray.count > 0) {
        
        BinaryTreeNode *node = [dataArray objectAtIndex:0];
        [dataArray removeObjectAtIndex:0];
        
        [values addObject:@(node.value)];
        
        for (NSInteger i=node.dataArray.count; i>0; i--) {
            
            BinaryTreeNode *node1 = node.dataArray[i-1];
            [dataArray insertObject:node1 atIndex:0];
        }
    }
    
    return values;
}

验证

{
        /*
         输入：root = [1,null,3,2,4,null,5,6]
         输出：[1,3,5,6,2,4]
         */
        
        BinaryTreeNode *node1 = [[BinaryTreeNode alloc] init];
        node1.value = 1;
        
        BinaryTreeNode *node2 = [[BinaryTreeNode alloc] init];
        node2.value = 3;
        
        BinaryTreeNode *node3 = [[BinaryTreeNode alloc] init];
        node3.value = 2;
        
        BinaryTreeNode *node4 = [[BinaryTreeNode alloc] init];
        node4.value = 4;
        
        node1.dataArray = @[node2, node3, node4];
        
        
        BinaryTreeNode *node5 = [[BinaryTreeNode alloc] init];
        node5.value = 5;
        
        BinaryTreeNode *node6 = [[BinaryTreeNode alloc] init];
        node6.value = 6;
        
        node2.dataArray = @[node5, node6];

        NSArray *arr1 = [self preorder1:node1];
        NSLog(@"arr1 is %@",arr1);
        
        NSArray *arr2 = [self preorder2:node1];
        NSLog(@"arr2 is %@",arr2);
    }
    
    {
        /*
         输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
         输出：[1,2,3,6,7,11,14,4,8,12,5,9,13,10]
         */
        
        BinaryTreeNode *node1 = [[BinaryTreeNode alloc] init];
        node1.value = 1;
        
        BinaryTreeNode *node2 = [[BinaryTreeNode alloc] init];
        node2.value = 2;
        
        BinaryTreeNode *node3 = [[BinaryTreeNode alloc] init];
        node3.value = 3;
        
        BinaryTreeNode *node4 = [[BinaryTreeNode alloc] init];
        node4.value = 4;
        
        BinaryTreeNode *node5 = [[BinaryTreeNode alloc] init];
        node5.value = 5;
        
        node1.dataArray = @[node2, node3, node4, node5];
        
        
        BinaryTreeNode *node6 = [[BinaryTreeNode alloc] init];
        node6.value = 6;
        
        BinaryTreeNode *node7 = [[BinaryTreeNode alloc] init];
        node7.value = 7;
        
        node3.dataArray = @[node6, node7];

        
        BinaryTreeNode *node8 = [[BinaryTreeNode alloc] init];
        node8.value = 8;
        
        node4.dataArray = @[node8];

        
        BinaryTreeNode *node9 = [[BinaryTreeNode alloc] init];
        node9.value = 9;
        
        BinaryTreeNode *node10 = [[BinaryTreeNode alloc] init];
        node10.value = 10;
        
        node5.dataArray = @[node9, node10];

        
        BinaryTreeNode *node11 = [[BinaryTreeNode alloc] init];
        node11.value = 11;
        
        node7.dataArray = @[node11];

        
        BinaryTreeNode *node12 = [[BinaryTreeNode alloc] init];
        node12.value = 12;
        
        node8.dataArray = @[node12];

        
        BinaryTreeNode *node13 = [[BinaryTreeNode alloc] init];
        node13.value = 13;
        
        node9.dataArray = @[node13];

        
        BinaryTreeNode *node14 = [[BinaryTreeNode alloc] init];
        node14.value = 14;
        
        node11.dataArray = @[node14];

        
        NSArray *arr1 = [self preorder1:node1];
        NSLog(@"arr1 is %@",arr1);
        
        NSArray *arr2 = [self preorder2:node1];
        NSLog(@"arr2 is %@",arr2);
    }