104.二叉树的最大深度.md

104.二叉树的最大深度

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

// @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 maxDepth(root: TreeNode | null): number {}
// @lc code=end

解法 1: 递归

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

function maxDepth(root: TreeNode | null): number {
  if (!root) return 0
  const left = maxDepth(root.left)
  const right = maxDepth(root.right)

  return Math.max(left, right) + 1
}

解法 2: 迭代

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

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

  let deep = 0
  let children = [root]
  while (children.length) {
    let tmp = children
    children = []
    for (const item of tmp) {
      if (item.left) children.push(item.left)
      if (item.right) children.push(item.right)
    }
    deep++
  }
  return deep
}

解法 3: bfs

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

function maxDepth(root: TreeNode | null): number {
  const bfs = (nodes: TreeNode[], depth = 0): number => {
    if (!nodes.length) return depth

    let tmp: TreeNode[] = []
    for (const node of nodes) {
      node?.left && tmp.push(node.left)
      node?.right && tmp.push(node.right)
    }
    return bfs(tmp, depth + 1)
  }
  return bfs(root ? [root] : [])
}

Case

test.each([{ input: { root: [3, 9, 20, null, null, 15, 7] }, output: 3 }])(
  `input: root = $input.root`,
  ({ input: { root }, output }) => {
    const rootNode = BinaryTree.deserialize(root)
    expect(maxDepth(rootNode)).toBe(output)
  },
)