题意

求给定二叉树深度。

思路

我们可以参考类似一题，只不过节点的值全部都为1，只需要从根节点搜索到叶子节点就可以得到结果。

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    int dfs(TreeNode* now)
    {
        if(now == NULL) return 0;//若当前节点不存在，返回0
        if(now->left == NULL && now->right == NULL) return 1;
        return max(dfs(now->right),dfs(now->left))+1;//否则继续搜索左右子树
    }
    int maxDepth(TreeNode* root)
    {
        // write code here
        return dfs(root);//返回搜索结果
    }
};

复杂度分析

时间复杂度：$O(n)O(n)$,$nn$是二叉树的节点个数，由于要计算深度，每个节点都必须搜索到。

空间复杂度：$O(H)O(H)$,其中$HH$代表二叉树最大深度，只需要$O(H)O(H)$的栈空间。