111.二叉树的最小深度

链接：111.二叉树的最小深度
难度：Easy
标签：树、深度优先搜索、广度优先搜索、二叉树
简介：给定一个二叉树，找出其最小深度。

题解 1 - typescript

• 编辑时间：2020-08-21
• 执行用时：92ms
• 内存消耗：42.3MB
• 编程语言：typescript
• 解法介绍：深度优先。

function minDepth(root: TreeNode | null): number {
  if (root === null) return 0;
  else if (root.left === null && root.right === null) return 1;
  else {
    let minD = Infinity;
    if (root.left) minD = Math.min(minDepth(root.left), minD);
    if (root.right) minD = Math.min(minDepth(root.right), minD);
    return minD + 1;
  }
}

题解 2 - typescript

• 编辑时间：2020-08-21
• 执行用时：88ms
• 内存消耗：41.6MB
• 编程语言：typescript
• 解法介绍：广度优先。

function minDepth(root: TreeNode | null): number {
  if (root === null) return 0;
  const queue: TreeNode[] = [root];
  let height = 1;
  let size = 1;
  while (queue.length !== 0) {
    const node = queue.shift() as TreeNode;
    if (node.left === null && node.right === null) return height;
    if (node.left !== null) queue.push(node.left);
    if (node.right !== null) queue.push(node.right);
    if (--size === 0) {
      height++;
      size = queue.length;
    }
  }
  return 0;
}

题解 3 - c

• 编辑时间：2021-11-27
• 执行用时：132ms
• 内存消耗：73.8MB
• 编程语言：c
• 解法介绍：递归。

// 递归遍历每个节点
void inorder(struct TreeNode *root, int level, int *min){
    if (!root) return ;
    // 如果是叶子且层级比较小则赋值
    if (!root->left && !root->right) {
        if (*min > level) *min = level;
        return ;
    }
    inorder(root->left, level + 1, min);
    inorder(root->right, level + 1, min);
}
int minDepth(struct TreeNode* root){
    if (!root) return 0;
    int min = 10000;
    inorder(root, 1, &min);
    return min;
}