题解 | 二叉树的最大深度

/**

 * 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) {

        if (root == nullptr) {

            return 0;

        }

        int left_depth = maxDepth(root->left);

        int right_depth = maxDepth(root->right);

        return 1 + max(left_depth, right_depth);

    }

};

class Solution {
public:
    int maxDepth(TreeNode* root) {
        //空节点没有深度
        if(root == NULL)
            return 0;
        //队列维护层次后续节点
        queue<TreeNode*> q;
        //根入队
        q.push(root);
        //记录深度
        int res = 0;
        //层次遍历
        while(!q.empty()){
            //记录当前层有多少节点
            int n = q.size();
            //遍历完这一层，再进入下一层
            for(int i = 0; i < n; i++){
                TreeNode* node = q.front();
                q.pop();
                //添加下一层的左右节点
                if(node->left)
                    q.push(node->left);
                if(node->right)
                    q.push(node->right);
            }
            //深度加1
            res++;
        }
        return res;
    }
};