【牛客刷题-算法】 NC13 二叉树的最大深度

1.题目描述

描述

求给定二叉树的最大深度，

深度是指树的根节点到任一叶子节点路径上节点的数量。

最大深度是所有叶子节点的深度的最大值。

（注：叶子节点是指没有子节点的节点。）

数据范围：0 ≤ n ≤ 100000 0≤n≤1000000≤n≤100000，树上每个节点的val满足 ∣ v a l ∣ ≤ 100 ∣val∣≤100∣val∣≤100

要求： 空间复杂度 O ( 1 ) O ( 1 ) O(1)O(1)O(1)O(1),时间复杂度 O ( n ) O ( n ) O(n)O(n)O(n)O(n)

注：示例中的输入是按照二叉树的层序遍历顺序，# 表示空。

2.算法设计思路

可以用递归的思路来解这个问题：

二叉树的最大深度 = m a x { 左子树最大深度，右子树最大深度 } + 1 二叉树的最大深度 = max\{左子树最大深度，右子树最大深度\}+1二叉树的最大深度=max{左子树最大深度，右子树最大深度}+1

而对于左右子树的最大深度，我们也同样地使用上面的表达式计算。

直到递归到空的树，此时它的深度为 0 ，开始回升。

3.算法实现

注：这里并不是完整代码，而只是核心代码的模式

使用编程语言：C++

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 * };
 */
class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int maxDepth(TreeNode* root) {
        //到达叶子结点
        if(root == nullptr) return 0;
        int max = 0;
        int deep1 = maxDepth(root->left) + 1;
        int deep2 = maxDepth(root->right) + 1;
        if(deep1 > deep2) max = deep1;
        else max = deep2;
        return max;
    }
};

4.运行结果

成功通过！

结束语：

今天的分享就到这里啦，快来加入刷题大军叭！