算法(TS)：二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例一

输出：[[3],[9,20],[15,7]]

提示：

• 树中节点数目在范围 [0, 2000] 内
• -1000 <= Node.val <= 1000

解法

解法一

维护一个队列存放二叉树中的节点，同一层的节点从左到右连续放在一起。先将root放入队列，外层循环用while语句判断队列是否为空，将队列当前的长度保存在一个变量 size 中，size的值是本层节点的个数，内层循环用 while 判断size是否为0，在内层循环体中取出队首的节点node，将node的值push到需要返回的数据中，并将node.left 和 node.right push 到队尾。实现如下：

/**
 * 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 levelOrder(root: TreeNode | null): number[][] {
    if (!root) return []
    const stack: TreeNode[] = [root]
    const result: number[][] = []
    while(stack.length) {
        let size = stack.length
        const values:number[] = []
        while(size) {
            const node = stack.shift()
            values.push(node.val)
            if(node.left) {
                stack.push(node.left)
            }
            if (node.right) {
                stack.push(node.right)
            }
            size--
        }

        result.push(values)
    }

    return result
};

时间复杂度O(n)，空间复杂度O(n)

解法二

用递归改造解法一。将解法一中的外层while和队列用递归代替

/**
 * 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 levelOrder(root: TreeNode | null): number[][] {
    const result: number[][] = []
    const conputed = (nodes: TreeNode[],values:number[][]) => {
        const levelValues: number[] = []
        const childrens: TreeNode[] = []
        while(nodes.length) {
            const node = nodes.shift()
            levelValues.push(node.val)
            if (node.left) {
                childrens.push(node.left)
            }
            if (node.right) {
                childrens.push(node.right)
            }
        }
        if (levelValues.length) {
            values.push(levelValues)
        }
        if (childrens.length) {
            conputed(childrens,values)
        }
    }

    if (root) {
        conputed([root],result)
    }
    return result
};

时间复杂度O(n)，递归需要占用栈空间，空间复杂度O(height)，height 是二叉树的最大深度