题解 | #二叉树的最大深度#

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

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int maxDepth(TreeNode* root) {
        // write code here
        //空节点没有深度
        if(!root)
            return 0;
        //返回子树深度+1
        return max(maxDepth(root->left),maxDepth(root->right))+1;
    }
};

利用递归来解决：

• 终止条件： 当进入叶子节点后，再进入子节点，即为空，没有深度可言，返回0.
• 返回值： 每一级按照上述公式，返回两边子树深度的最大值加上本级的深度，即加1.
• 本级任务： 每一级的任务就是进入左右子树，求左右子树的深度。

具体做法：

• step 1：对于每个节点，若是不为空才能累计一次深度，若是为空，返回深度为0.
• step 2：递归分别计算左子树与右子树的深度。
• step 3：当前深度为两个子树深度较大值再加1。