每日一题——二叉树的最大深度

题目

求给定二叉树的最大深度，
深度是指树的根节点到任一叶子节点路径上节点的数量。
最大深度是所有叶子节点的深度的最大值。

数据范围：0≤n≤100000，树上每个节点的val满足 ∣val∣≤100

要求： 空间复杂度 O(1),时间复杂度 O(n)

思路

二叉树的深度就等于根节点这个1层加上左子树和右子树深度的最大值，即
root_depth=max(left_depth, right_depth)+1。而每个子树我们都可以看成一个根节点，使用递归即可求的深度。

解答代码

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * @param root TreeNode类 
     * @return int整型
     */
    int maxDepth(TreeNode* root) {
        // write code here
        if (root == nullptr) {
            return 0;
        }

        return std::max(maxDepth(root->right), maxDepth(root->left)) + 1;
    }
};