小旭讲解 LeetCode 104. 二叉树的最大深度
文章目录

  • 原题
  • 思路一 – DFS
  • 思路二 – BFS
  • 参考

原题

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

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

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

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

    3    /    9  20     /      15   7

返回它的最大深度 3 。

思路一 – DFS

代码

class Solution { public:     int maxDepth(TreeNode* u) {         if (u == nullptr) return 0;         if (u->left == nullptr && u->right == nullptr) return 1;         int ldep = 0, rdep = 0;         if (u->left != nullptr) ldep = maxDepth(u->left) + 1;         if (u->right != nullptr) rdep = maxDepth(u->right) + 1;         return max(ldep, rdep);     } };

复杂度分析

时间复杂度:O(n) 树节点的个数
空间复杂度:O(h) h 树的最大高度

思路二 – BFS

class Solution { public:     int maxDepth(TreeNode* root) {         if (root == nullptr) return 0;         queue<TreeNode*> q;         q.push(root);         int ans = 0;         while (!q.empty()) {             ++ans;             int l = q.size();             while (l--) {                 auto node = q.front();                 q.pop();                 if (node->left != nullptr) q.push(node->left);                 if (node->right != nullptr) q.push(node->right);             }         }         return ans;     } };

复杂度分析

时间复杂度:O(n)
空间复杂度:O(n) 二叉树的叶子节点上限为 n / 2,故空间复杂度的上限为O(n)

参考

[1]. LeetCode 原题. https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

小旭讲解 LeetCode 104. 二叉树的最大深度leetcode刷题题解部分资料来自网络,侵权毕设源码联系删除

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 小旭讲解 LeetCode 104. 二叉树的最大深度leetcode刷题题解