二叉树遍历方式

先定义二叉树,从上到下,根节点为1,左叶为2,右叶为3;左叶2的下一级左叶为4,右叶为5,依次类推

• 层序遍历: [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ] 左右横线左右横线
• 前序遍历: [ 1, 2, 4, 7, 8, 5, 3, 6, 9, 10 ] 左下右上左下右上斜线
• 中序遍历: [ 7, 4, 8, 2, 5, 1, 3, 9, 6, 10 ] 上下竖线 从左到右
• 后序遍历: [ 7, 8, 4, 5, 2, 9, 10, 6, 3, 1 ] 暂不理解

代码实现

class TreeNode<T = number> {
    val: T;
    left: TreeNode<T> | null = null;
    right: TreeNode<T> | null = null;

    constructor(val: T) {
        this.val = val;
    }
}
/* 层序遍历 
使用队列, 利用队列（Queue）的「先进先出（FIFO）」特性
1. 先存入根节点,根节点出列,将根节点的值存入数组
2.再分别压入左右子节点到队列 3. 重新执行  取出首位节点,出列及存入节点的值
3. 这里利用数组queue按顺序存入每一层的节点, 按序取出当前节点后,又分别按左右顺序依次存入子节点
思考: 像递归但不是, 递归是隐式使用栈,一路到底
*/
function levelOrder(root: TreeNode | null): number[] {
    // 初始化队列，加入根节点
    const queue = [root];
    // 初始化一个列表，用于保存遍历序列
    const list: number[] = [];
    while (queue.length) {
        let node = queue.shift() as TreeNode; // 队列出队
        list.push(node.val); // 保存节点值
        if (node.left) {
            queue.push(node.left); // 左子节点入队
        }
        if (node.right) {
            queue.push(node.right); // 右子节点入队
        }
    }
    return list;
}

/**
* 递归实现层序遍历 - 返回一维平面数组（正确版本）
* 顺序：从上到下，从左到右 → [1, 2, 3, 4, 5, 6, 7]
*/
levelOrderRecursiveFlat(root: TreeNode<T> | null): T[] {
        const result: T[] = [];
        const dfs = (node: TreeNode<T> | null, level: number): void => {
            if (!node) return;
            // 关键：使用 level 作为索引，确保同一层的节点按出现顺序放入对应位置
            if (result.length === level) {
                result[level] = [];           // 如果这一层还没有数组，就创建一个
            }
            // 把当前节点值放入对应层
            result[level].push(node.val);
            // 继续递归左右子树，层级 + 1
            dfs(node.left, level + 1);
            dfs(node.right, level + 1);
        };
        dfs(root, 0);
        // 最后把二维数组展平为一维
        return result.flat();
    }

/* 前序遍历 */
function preOrder(root: TreeNode | null,list: number[]): void {
    if (root === null) {
        return ;
    }
    // 访问优先级：根节点 -> 左子树 -> 右子树
    // 深入到最底部左子树然后最底部右子树,再上一层右子树...
    list.push(root.val);
    preOrder(root.left, list);
    preOrder(root.right, list);
}


// 非递归前序遍历（使用栈）
    preorderIterative(root: TreeNode | null): T[] {
        const result: T[] = [];
        if (!root) return result;
        const stack: TreeNode<T>[] = [this.root];
        while (stack.length > 0) {
            const node = stack.pop()!;
            result.push(node.val);
            if (node.right) stack.push(node.right);   // 先右后左，保证左先被处理 与pop搭配
            if (node.left) stack.push(node.left);
        }
        return result;
    }

/* 中序遍历 */
function inOrder(root: TreeNode | null,list: number[]): void {
    if (root === null) {
        return;
    }
    // 访问优先级：左子树 -> 根节点 -> 右子树
    inOrder(root.left, list);
    list.push(root.val);
    inOrder(root.right, list);
}

/* 后序遍历 */
function postOrder(root: TreeNode | null,list: number[]): void {
    if (root === null) {
        return;
    }
    // 访问优先级：左子树 -> 右子树 -> 根节点
    postOrder(root.left, list);
    postOrder(root.right, list);
    list.push(root.val);
}