算法:二叉树的层序遍历II
前言
什么是层序遍历II
层序遍历II和二叉树的层序遍历一致,从上到下,从左到右依次打印每个节点中存储的数据,在最后返回前将result向量翻转即可。
如下图所示的数据结构:
对比四种遍历方式:
前序遍历:A → B → D → C
中序遍历:B → D → A → C
后续遍历:D → B → C → A
层序遍历:A → B → C → D
层序遍历II:A → B → C → D
题目
给定一个二叉树,返回其节点值自底向上的层序遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
例如: 给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回其自底向上的层序遍历为: [ [15,7], [9,20], [3] ]复制代码
附:leetcode-cn.com/problems/bi…
思路和分析
用一个变量记录当前所在的层
数组的下标即为当前所在的层
如果是第一次进入该层,
创建一个空数组
否则将节点值添加到该层的数组中
返回数组
将返回的数组反转就是最后的结果
总结一句话:队列的每个元素记录深度。相同深度组成一个数组返回即可,最后反转数组
解题
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {number[][]} */ var levelOrderBottom = function(root) { if(root == null) { return [] } let result = [] let queue = [root] while (queue.length) { let levelSize = queue.length; // 当前层级的结果 let curLevelResult = []; // 遍历当前层级的结果 for (let i = 0; i < levelSize; i++) { const node = queue.shift(); curLevelResult.push(node.val); if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } // 倒序插入数组(反转结果数组) result.unshift(curLevelResult); } return result; };
作者:forever_Mamba
链接:https://juejin.cn/post/7030785275844362253