心之所向便是光

Leetcode 104.二叉树的最大深度

  • 2021-06-23
  • 作者 Ender
  • 1438 字
  • 次阅读

题目描述：

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

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

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

示例：

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

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

返回它的最大深度 3 。

链接：

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

题目分析

1.广度优先搜索

  从 Leetcode 102.二叉树的层序遍历 我们可以很容易想到这个算法。层序遍历题目中对于每一层都需要新开一行进行存储，直接改成计数即可，代码比层序遍历更简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root) return 0;

        int result = 0;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            result++;
            int levelsize = q.size();
            while(levelsize--){
                TreeNode *p = q.front();
                q.pop();
                if(p->left) q.push(p->left);
                if(p->right) q.push(p->right);
            }
        }
        return result;
    }
};

  时间复杂度：$O(n)$，其中 $n$ 为二叉树的结点数。我们对二叉树进行了一次遍历。
  空间复杂度：$O(n)$，其中 $n$ 为二叉树的结点数。队列的最大长度为 $n$。

2.深度优先搜索

  搜索树的深度其实更常用的是深度优先搜索，只需要一个递归的过程即可完成，每一个结点从左右子树中选择深度更深的一边并加上自身往上返回即可。

1
2
3
4
5
6
7
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root) return 0;
        return max(maxDepth(root->left), maxDepth(root->right))+1;
    }
};

  时间复杂度：$O(n)$，其中 $n$ 为二叉树的结点数。我们对二叉树进行了一次遍历。
  空间复杂度：$O(n)$，其中 $n$ 为二叉树的结点数。空间复杂度取决于栈的深度。在最坏情况下（树是一条链）栈的深度会达到 $n$，最好情况下（树是平衡的）则是 $O(\log n)$。

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
, , , , ,
最后编辑：2021-06-23