二叉树的最大深度

举报
Linux猿 发表于 2021/12/11 22:38:55 2021/12/11
【摘要】 CSDN博客专家🏆,华为云享专家🏆,Linux、C/C++、面试、刷题、算法尽管咨询我,关注我,有问题私聊! 欢迎小伙伴们点赞👍、收藏⭐、留言💬

🎈 作者:Linux猿

🎈 简介:CSDN博客专家🏆,华为云享专家🏆,Linux、C/C++、面试、刷题、算法尽管咨询我,关注我,有问题私聊!

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬


一、题目描述

给定一个二叉树,找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

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

二、测试样例

给定如下所示的二叉树:

 上图中,二叉树的最大深度为 3。

三、解题思路

本题考查对深度优先搜索的应用,当然,也可以使用栈来模拟深度优先搜索。搜索的过程中比较左右子树的深度,返回较深的一个。

四、代码实现

#include <iostream>
#include <stack>
using namespace std;
struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    int FindMaxDepth(TreeNode* root, int dep) {
        if(!root) return dep;
        return max(FindMaxDepth(root->left, dep), FindMaxDepth(root->right, dep)) + 1;
    }
    int maxDepth(TreeNode* root) {
        if(!root) return 0;
        return FindMaxDepth(root, 0);
    }
};

int main() {
    TreeNode* root = new(TreeNode);
    TreeNode* node1 = new(TreeNode);
    TreeNode* node2 = new(TreeNode);
    root->left = nullptr;
    root->right = nullptr;
    // root->left = node1;
    // root->right = node2;
    // node1->left = nullptr;
    // node1->right = nullptr;
    // node2->left = nullptr;
    // node2->right = nullptr;
    Solution obj;
    int ans = obj.maxDepth(root);
    cout<<"length = "<<ans<<endl;
}

五、复杂度分析

5.1 时间复杂度

时间复杂度为:O(n),求二叉树的最大深度,需要遍历二叉树的所有节点,故时间复杂度为 O(n)。

5.2 空间复杂度

空间复杂度为:O(m),这里空间复杂度最大为栈的深度,同时也是二叉树的最大深度,空间复杂度最大为 O(n)。

六、总结

本题考查对深度优先搜索的理解,需要掌握递归和非递归两种方式。


CSDN博客专家🏆,华为云享专家🏆,Linux、C/C++、面试、刷题、算法尽管咨询我,关注我,有问题私聊!

欢迎小伙伴们点赞👍、收藏⭐、留言💬


【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200