二叉树的深度

二叉树的最大深度

  // 递归解法
  int maxDepth(TreeNode *root) {
    // 递归边界条件
    if (root == nullptr) return 0;
    // 计算左节点深度
    int left_len = maxDepth(root->left);
    // 计算右节点深度
    int right_len = maxDepth(root->right);
    // 计算最大深度
    return max(left_len, right_len) + 1;
  }

二叉树的最小深度

  // 叶子节点/只有左子节点/只有右子节点/两边都有
  int minDepthDFS(TreeNode *root) {
    if (root == nullptr) return 0;
    if (root->left == nullptr && root->right == nullptr) return 1;
    if (root->left == nullptr) return minDepth(root->right) + 1;
    if (root->right == nullptr) return minDepth(root->left) + 1;
    return min(minDepth(root->left), minDepth(root->right)) + 1;
  }

  // BFS做法，需要涉及队列
  int minDepthBFS(TreeNode *root) {
    if (root == nullptr) return 0;

    // 还有一个办法，把 depth 也打到 queue 里，变成 queue<pair<TreeNode*, int>>
    // 这样就不用两层循环
    queue<TreeNode *> q;
    q.push(root);
    int depth = 1;

    while (!q.empty()) {
      int level_size = q.size();
      for (int i = 0; i < level_size; ++i) {
        TreeNode *node = q.front();
        q.pop();

        // 找到叶子节点
        if (node->left == nullptr && node->right == nullptr) {
          return depth;
        }

        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
      }
      depth++;
    }
    return depth;
  }