【2024考研】题解17 | #二叉树的最大深度#简谐美

#include <algorithm>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int maxDepth(TreeNode* root) {
        // write code here
        if(root == nullptr) return 0;
        //加的这个1是我的理解诶是算上了根0，着实优雅
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};  

时间复杂度：

O(n)，其中n是二叉树的节点个数。每个节点都需要遍历一次。

空间复杂度：

O(h)，其中h是二叉树的高度。递归调用栈的最大深度是二叉树的高度。

基本算法思想：

使用递归的方式求解二叉树的最大深度。

递归函数的定义是返回以当前节点为根节点的子树的最大深度。

递归函数的终止条件是当前节点为空，返回0。

递归函数的返回结果是左子树的最大深度和右子树的最大深度的较大值加1。

注：加1是因为在计算二叉树的深度时，需要把当前节点也算上。所以在递归函数中，每次返回的是左子树和右子树的深度的较大值加1，表示当前节点的深度。这样就可以递归地计算出整棵二叉树的深度了。