leetcode-559. N叉树的最大深度(OC)

N叉树的最大深度

地址:https://leetcode-cn.com/problems/maximum-depth-of-n-ary-tree/

给定一个 N 叉树，找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。

示例 1：
输入：root = [1,null,3,2,4,null,5,6]
输出：3

示例 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]
输出：5

提示：
树的深度不会超过 1000 。
树的节点数目位于 [0, 104] 之间。

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

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

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

递归

- (NSInteger)maxDepth1:(BinaryTreeNode *)root
{
    if (root == nil) {
        return 0;
    }
    
    if (root.dataArray.count == 0) {
        return 1;
    }
    
    NSInteger max = 0;
        
    for (BinaryTreeNode *node in root.dataArray) {
        NSInteger depth = [self maxDepth1:node];
        max = MAX(max, depth);
    }
    
    return max + 1;
}

迭代

- (NSInteger)maxDepth2:(BinaryTreeNode *)root
{
    if (root == nil) {
        return 0;
    }
    
    NSMutableArray *dataArray = [NSMutableArray array];
    
    [dataArray addObject:root];
    
    NSInteger count = dataArray.count;
    
    NSInteger max = 0;
    
    while (dataArray.count > 0) {
        
        BinaryTreeNode *node = [dataArray firstObject];
        [dataArray removeObjectAtIndex:0];
        count --;
        
        if (node.dataArray.count > 0) {
            [dataArray addObjectsFromArray:node.dataArray];
        }
        
        if (count == 0) {
            
            count = dataArray.count;
            max ++;
        }
    }
    
    return max;
}

验证

{
        /*
         输入：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];

        NSInteger depath1 = [self maxDepth1:node1];
        NSLog(@"depath1 is %ld",depath1);
        
        NSInteger depath2 = [self maxDepth2:node1];
        NSLog(@"depath2 is %ld",depath2);
    }
    
    {
        /*
         输入：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];

        NSInteger depath1 = [self maxDepth1:node1];
        NSLog(@"depath1 is %ld",depath1);
        
        NSInteger depath2 = [self maxDepth2:node1];
        NSLog(@"depath2 is %ld",depath2);
    }