leetcode-104.二叉树的最大深度(OC)

二叉树的最大深度

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

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

3

/
9 20
/
15 7
返回它的最大深度 3 。

方法1:递归

左子树和右子树的最大高度 + 1

- (NSInteger)maxDepth1:(BinaryTreeNode *)root
{
    if (root == nil) {
        return 0;
    }
    
    if (root.leftNode == nil && root.rightNode == nil) {
        return 1;
    }
    
    NSInteger left = [self maxDepth1:root.leftNode];
    
    NSInteger right = [self maxDepth1:root.rightNode];

    return MAX(left, right) + 1;
}

方法2:迭代

迭代方法就是使用层序遍历 一共有多少层 就是高度多少
count表示每层的数量 开始时为1 也就是根节点，每次数组减少时 count都减少
当count为0时，即为一层遍历完 高度maxH+1

//迭代
- (NSInteger)maxDepth2:(BinaryTreeNode *)root
{
    if (root == nil) {
        return 0;
    }
 
    NSMutableArray *dataArray = [NSMutableArray array];
    
    [dataArray addObject:root];
    
    NSInteger count = dataArray.count;
    
    NSInteger maxH = 0;
    
    while (dataArray.count > 0) {
       
        BinaryTreeNode *node = [dataArray firstObject];
        [dataArray removeObjectAtIndex:0];
        count--;
        
        if (node.leftNode) {
            [dataArray addObject:node.leftNode];
        }
        
        if (node.rightNode) {
            [dataArray addObject:node.rightNode];
        }
        
        if (count == 0) {
            count = dataArray.count;
            maxH++;
        }
    }
    
    return maxH;
}