H's Blogs
0%

发表于 更新于 分类于 本文字数： 200 阅读时长 ≈ 1 分钟

题目：

给定一个二叉树 root ，返回其最大深度。

二叉树的最大深度

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
//方法一：递归，返回子节点的最大深度+1
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root){return0;}
        return max(maxDepth(root->left),maxDepth(root->right))+1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//方法一：递归，维护一个全局变量，递归到子节点+1，返回最大值
class Solution {
public:
    int maxDepth(TreeNode* root) {
        int result = 0;
        function<void(TreeNode* ,int )> def = [&result,&def](TreeNode* root,int count){
            if(!root){
                return;
            }
            count +=1;
            result = max(result,count);
            def(root->left,count);
            def(root->right,count);
        };
        def(root,0);
        return result;
    }
};