leetcode-590. N叉树的后序遍历(OC)

N叉树的后序遍历

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

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

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

 示例 1：
 输入：root = [1,null,3,2,4,null,5,6]
 输出：[5,6,3,2,4,1]
 
 示例 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]
 输出：[2,6,14,11,7,3,12,8,4,13,9,10,5,1]

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

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

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

递归

很简单 上代码吧

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

迭代

- (NSArray *)postorder2:(BinaryTreeNode *)root
{
    /*
     重点是 加入数组 取出最后一个
     每次值都加入到数组的第0个
     */
    
    if (root == nil) {
        return @[];
    }
    
    NSMutableArray *values = [NSMutableArray array];

    NSMutableArray *dataArray = [NSMutableArray array];
    [dataArray addObject:root];
    
    while (dataArray.count > 0) {
        
        BinaryTreeNode *node = [dataArray lastObject];
        [dataArray removeLastObject];

        for (BinaryTreeNode *node1 in node.dataArray) {
            [dataArray addObject:node1];
        }
        
        [values insertObject:@(node.value) 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 postorder1:node1];
        NSLog(@"arr1 is %@",arr1);
        
        NSArray *arr2 = [self postorder2: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 postorder1:node1];
        NSLog(@"arr1 is %@",arr1);
        
        NSArray *arr2 = [self postorder2:node1];
        NSLog(@"arr2 is %@",arr2);
    }