111.二叉树的最小深度.md

111.二叉树的最小深度

/*
 * @lc app=leetcode.cn id=111 lang=typescript
 *
 * [111] 二叉树的最小深度
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function minDepth(root: TreeNode | null): number {}
// @lc code=end

解法 1:递归

• 时间复杂度:
• 空间复杂度:

function minDepth(root: Array<TreeNode> | TreeNode | null): number {
  if (!root) return 0
  if (!Array.isArray(root)) root = [root]
  const children: Array<TreeNode> = []
  for (const node of root) {
    if (!node.left && !node.right) return 1
    children.push(...[node.left!, node.right!].filter(Boolean))
  }
  return minDepth(children) + 1
}

解法 2: 迭代

• 时间复杂度:
• 空间复杂度:

function minDepth(root: TreeNode | null): number {
  if (!root) return 0

  let deep = 0
  let children = [root]
  while (children.length) {
    const tmp = children
    children = []
    deep++

    for (const node of tmp) {
      if (!node.left && !node.right) return deep
      children.push(...[node.left!, node.right!].filter(Boolean))
    }
  }
  return deep
}

Case

test.each([
  { input: { root: [3, 9, 20, null, null, 15, 7] }, output: 2 },
  { input: { root: [2, null, 3, null, 4, null, 5, null, 6] }, output: 5 },
])('input: root = $input.root', ({ input: { root }, output }) => {
  const rootNode = BinaryTree.deserialize(root)
  expect(minDepth(rootNode)).toEqual(output)
})