二叉树的最大深度

层次遍历

/**
 * 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) {
       
        TreeNode* node ; //迭代节点
        queue<TreeNode*> my_que; //队列
        int result = 0;
        if(root == nullptr) return result;
        else // 根节点进队列
        {
            my_que.push(root);
        }

        while(my_que.empty() != 1)
        {
            int size = my_que.size();
         	result +=1;//计算层级数量
            for(int i=0 ; i<size ; i++) 
            {
                node = my_que.front(); //该层级的点弹出放入数组
                my_que.pop();
             
                //每一个弹出点的下一个层级左右节点压入队列
                if(node->left != nullptr)    my_que.push(node->left);
                if(node->right != nullptr)   my_que.push(node->right);

            }
           
        }
        return result;

    }
};

递归遍历

/**
 * 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 getdepth(TreeNode* root)
    {
        if(root==nullptr) return 0;
        int left_depth = getdepth(root->left);
        int right_depth = getdepth(root->right);

        return 1+max(left_depth , right_depth);
    }
    int maxDepth(TreeNode* root) {

        if(root == nullptr) return 0;

        return getdepth(root);
    }
};

二刷

/**
 * 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;
        int left_deep = maxDepth(root->left);
        int right_deep = maxDepth(root->right);
        return max(left_deep,right_deep) + 1;
    }
};

高频题

/**
 * 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 track_back(TreeNode* cur)
    {
        if(cur == nullptr) return 0;
        return max( track_back(cur->left) ,  track_back(cur->right) ) + 1;
    }
    int maxDepth(TreeNode* root) {
        return track_back(root);
    }
};