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

又是层次遍历的运用

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

class Solution {
public:
      //  层次遍历，记录最多有多少层
    int maxDepth(TreeNode* root) {
      if (root == nullptr) {
        return 0;
      }
      
      std::queue<TreeNode *> queue_;
      int count = 0;
      
      queue_.push(root);
      
      while (!queue_.empty()) {
        int size = queue_.size();
        
        for (int i = 0; i < size; ++i) {
          TreeNode *ptr = queue_.front();
          queue_.pop();
          if (ptr->left) {
            queue_.push(ptr->left);
          }
          if (ptr->right) {
            queue_.push(ptr->right);
          }
        }
        
        ++count;
      }
      
      return count;
    }
};

贴上递归算法，毕竟太简洁太好懂了

class Solution {
public:
    int maxDepth(TreeNode* root) {
        //空节点没有深度
        if(root == nullptr) 
            return 0;
        //返回子树深度+1
        return std::max(maxDepth(root->left), maxDepth(root->right)) + 1; 
    }
};