N叉樹的后序遍歷

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

 給定一個 n 叉樹的根節(jié)點 root 宏浩，返回 其節(jié)點值的 后序遍歷 贼穆。

 n 叉樹 在輸入中按層序遍歷進行序列化表示肺蔚，每組子節(jié)點由空值 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 我們需要創(chuàng)建一個BinaryTreeNode節(jié)點model 里面的對象如下

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

/**
 * N節(jié)點
 */
@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
{
    /*
     重點是 加入數(shù)組 取出最后一個
     每次值都加入到數(shù)組的第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);
    }