111. 二叉树的最小深度

思路

可以先考虑广度优先遍历，因为深度优先遍历需要遍历出所有的节点，然后再取得最小值，这样子要获取所有的节点复杂度太大了

通过广度优先遍历得到如下结果

/**
 * 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 {
    if (!root) {
        return 0
    }

    const queue: TreeNode[] = [root]

    let deep = 0

    while (queue.length) {
        const node = queue.shift() as TreeNode
        console.log(node.val)

        if (node.left) {
            queue.push(node.left)
        }

        if (node.right) {
            queue.push(node.right)
        }
    }

    return deep
}

但这样子还不够，因为需要获取到层级

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

    const queue: [TreeNode, number][] = [[root, 1]]

    let deep = 0

    while (queue.length) {
        const [node, len] = queue.shift()!
        console.log(node.val, len)

        if (node.left) {
            queue.push([node.left, len + 1])
        }
        if (node.right) {
            queue.push([node.right, len + 1])
        }
    }

    return deep
}

代码

/**
 * 采用广度优先遍历来进行遍历
 */
function minDepth(root: TreeNode | null): number {
    if (!root) {
        return 0
    }

    const queue: [TreeNode, number][] = [[root, 1]]

    while (queue.length) {
        const [node, len] = queue.shift()!
        console.log(node.val, len)

        if (!node.left && !node.right) {
            return len
        }

        if (node.left) {
            queue.push([node.left, len + 1])
        }
        if (node.right) {
            queue.push([node.right, len + 1])
        }
    }

    return 0
}

复杂度分析

时间复杂度:

空间复杂度: