1 问题

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，
返回它的最大深度 3 。

2 解法

2.1 递归法

按照递归三部曲：
（1）确定递归函数的参数与返回值
递归函数需要求当前节点处的最大深度，因而函数返回值为最大深度（int），函数参数为当前节点。

int getDepth(TreeNode* node)

（2）确定递归终止条件
当前节点为空时，则递归结束，返回深度0。

if(node == nullptr)
	return 0;

（3）单层递归逻辑
先求它的左子树的深度，再求的右子树的深度，最后取左右深度最大的数值 再+1 （加1是因为算上当前中间节点）就是目前节点为根节点的树的深度。

//左子树的深度
int leftDepth = getDepth(node->left);
//右子树的深度
int rightDepth = getDepth(node->right);
//左右子树深度的最大值加上当前节点这一层即为当前节点的最大深度
return max(leftDepth, rightDepth) + 1;

2.2 迭代法

采用树的层序遍历，每遍历一层，记录下层数。

/**
 * 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) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == nullptr)
            return 0;
        queue<TreeNode*> que;
        que.push(root);
        int depth = 0;
        while(!que.empty())
        {
            int size = que.size();
            //记录深度
            depth++;
            //遍历一层
            for(int i = 0; i < size; i++)
            {
                TreeNode* node = que.front();
                que.pop();
                if(node->left)  que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        return depth;
    }
};