04二叉树层序遍历

1.层序遍历

题目

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

示例 1：


输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：


输入：root = [1]
输出：[[1]]

示例 3：


输入：root = []
输出：[]

提示：

树中节点数目在范围 [0, 2000] 内

1000 <= Node.val <= 1000

思路

深度优先遍历

递归方式遍历

stack迭代方式遍历

广度优先：层序遍历

需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

TS实现

队列存储


/**
 * 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 queue: TreeNode[] = [];
    const result: number[][] = [];
    if (!root) return result;
    // 根节点入队列
    queue.push(root);
    while(queue.length) {
        const size = queue.length; // 推入和推出都是按层来的
        const hierarchyArr: number[] = [];
        for (let i = 0; i < size; i++) {
            const top = queue.shift();
            hierarchyArr.push(top.val);
            if (top.left) queue.push(top.left);
            if (top.right) queue.push(top.right);
        }
        result.push(hierarchyArr)
    }
    return result
};

递归实现


/**
 * 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 order = (curNode: TreeNode, result: number[][], depth: number ) => {
        if (!curNode) return;
        if (result.length === depth) result.push([]);
        result[depth].push(curNode.val);
        if (curNode.left) order(curNode.left, result, depth + 1);
        if (curNode.right) order(curNode.right, result, depth + 1);
    }
    let depth = 0;
    order(root, result, depth);
    return result;
};

在这个递归函数中，result.size() == depth 的检查是为了确保在当前深度还没有对应的子数组时，为新的一层创建一个空数组。

具体原因如下：

层次结构: result 是一个二维数组，每个子数组对应于二叉树的一个深度。比如，result[0] 存储根节点的值，result[1] 存储第一层的节点值，依此类推。

动态扩展: 在递归过程中，depth 变量表示当前节点的深度。如果 result 的大小等于 depth，说明当前深度还没有被初始化（即没有添加对应的子数组）。因此，我们需要 push 一个空数组，以便在后续存储该层的节点值。

避免越界: 如果不进行这个检查，而直接访问 result[depth]，当 depth 对应的子数组还未创建时，会导致越界错误。因此，通过这个条件检查，确保每层都有一个有效的子数组来存储节点值。

总结：这一步确保了 result 能够动态适应树的深度结构，避免访问未初始化的数组

2.层序遍历2

题目

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）