[102] 二叉树的层序遍历 js [107] 二叉树的层序遍历 II

题目描述：[102] 二叉树的层序遍历

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

解题思路：

使用队列来记录每一层的节点，每次把该层的节点记录下来的时候，同时把他们的左右孩子放入队列

每一次循环开始的时候都会记录当前队列里的节点个数，此时队列里只有这一层的节点

遍历每一个节点，把他们的左右孩子塞进队列

解法一：

function levelOrder(root: TreeNode | null): number[][] {let queue = [root];let res = [];if (root === null) {return [];}while (queue.length) {// 每一次循环开始的时候队列里只有这一层的节点let floor = queue.length;res.push([]);for (let i = 0; i < floor; i++) {let cur = queue.shift();res[res?.length - 1].push(cur.val);if (cur.left) {queue.push(cur.left);}if (cur.right) {queue.push(cur.right);}}}return res;
};

用时：
    // Your runtime beats 70.69 % of typescript submissions
    // Your memory usage beats 27.87 % of typescript submissions (55 MB)

题目描述：[107] 二叉树的层序遍历 II

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

解题思路：

把自上而下的结果reverse一下

解法一（reverse 自上而下的结果）：

function levelOrderBottom(root: TreeNode | null): number[][] {
let queue = [root];let res = [];if (root === null) {return [];}while (queue.length) {// 每一次循环开始的时候队列里只有这一层的节点let floor = queue.length;res.push([]);for (let i = 0; i < floor; i++) {let cur = queue.shift();res[res?.length - 1].push(cur.val);if (cur.left) {queue.push(cur.left);}if (cur.right) {queue.push(cur.right);}}}return res.reverse();
}

用时：

// Your runtime beats 85.45 % of typescript submissions

// Your memory usage beats 5.45 % of typescript submissions (52.8 MB)

解法二（把每一行的节点从数组的头部塞进去）：

function levelOrderBottom(root: TreeNode | null): number[][] {let queue = [root];let res = [];if (root === null) {return [];}while (queue.length) {let floor = queue.length;res.unshift([]);for (let i = 0; i < floor; i++) {let cur = queue.shift();res[0].push(cur.val);if (cur.left) {queue.push(cur.left);}if (cur.right) {queue.push(cur.right);}}}return res;
}

用时：

// Your runtime beats 30.91 % of typescript submissions

// Your memory usage beats 16.36 % of typescript submissions (52.6 MB)