BM26 求二叉树的层序遍历

描述

给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）

例如：

给定的二叉树是{3,9,20,#,#,15,7}, bm26

该二叉树层序遍历的结果是

[[3],[9,20],[15,7]]

数据范围：二叉树的节点数满足 $1 \leq n \leq$

解法：

1、遍历到一个节点，将左右个孩子加入队列；

2、一次遍历二叉树的一层；

3、怎么确定能遍历一层：每次遍历队列，先记录队列的大小size，出队size次，这些值即为一层，存入res数组，并通过1、2将下一层的节点存入队列；

/*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)
 *     }
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return int整型一维数组
 */


export function postorderTraversal(root: TreeNode): number[] {
    // write code here
    var res: number[] = [];
    var stack: TreeNode[] = [];
    var pre: TreeNode;
    
    while(root || stack.length) {
        while(root) {
            stack.push(root)
            root = root.left;
        }
        var node = stack.pop();
//         如果该节点右节点不存在或右节点已经访问过了
        if(!node.right || node.right === pre) {
            res.push(node.val);
            pre = node;
        } else {
//             当前节点入栈
            stack.push(node);
            root = node.right;
        }
    }
    return res;
}

BM26 求二叉树的层序遍历 ​

描述 ​

解法： ​

BM26 求二叉树的层序遍历

描述

解法：