wordpress 文章回收站,网站建设与网页设计,北京网站设计方案,广州专业网站制作平台层次遍历#xff1a;又叫广度优先遍历。就是从根节点开始#xff0c;先访问根节点下面一层全部元素#xff0c;再访问之后的层次#xff0c;直到访问完二叉树的最后一层。 我们先看一下基础的层次遍历题#xff0c;力扣102题#xff1a;给你一个二叉树#xff0c;请你返… 层次遍历又叫广度优先遍历。就是从根节点开始先访问根节点下面一层全部元素再访问之后的层次直到访问完二叉树的最后一层。 我们先看一下基础的层次遍历题力扣102题给你一个二叉树请你返回其按层序遍历得到的节点值。(即逐层地从左到右访问所有节点)。 分析先将根节点root放到队列queue中接着遍历队列。遍历当前层次的节点时如果这个节点还有子节点就将其加入队列中如果当前层次遍历完了就将队列的长度重新指向新的队列长度sizeOfQueue,这时队列长度就是下一层的节点个数。 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[][]}* * */function levelOrder(root) {if (!root) {return [];}let result [];let queue [];queue.push(root);while (queue.length 0) {let size queue.length;const tempList [];for (let i 0; i size; i) {let t queue.shift();tempList.push(t.val);if (t.left ! null) {queue.push(t.left);}if (t.right ! null) {queue.push(t.right);}}result.push(tempList);}return result;}
在上一题的基础上我们看一下力扣515题给定一棵二叉树的根节点 root 请找出该二叉树中每一层的最大值。 分析这其实就是先进行层次遍历之后找出每一层的最大值即可。我们用一个变量maxValue来记录当前得到的最大值。和本层的每一个节点的值进行比较。 /*** param {TreeNode} root* return {number[]}* */
function largestValues(root) {if (!root) {return [];}const largestValues []; // 存放每一层的最大值let queue [root];while (queue.length 0) {let sizeOfQueue queue.length;let largestValue -Number.MAX_VALUE;while (sizeOfQueue 0) {sizeOfQueue--;const treeNode queue.shift();largestValue Math.max(largestValue, treeNode.val) // 比较大小if (treeNode.left ! null) {queue.push(treeNode.left);}if (treeNode.right ! null) {queue.push(treeNode.right);}}largestValues.push(largestValue); // 把每一层最大值加入存放最大值的数组}return largestValues;
}我们再来看一下力扣199题给给定一个二叉树的根节点 root想象自己站在它的右侧按照从顶部到底部的顺序返回从右侧所能看到的节点值。 **分析**这道题也是层次遍历的变种题我们思考一下既然需要我们找到每一层最右边节点的值那在我们遍历每一层节点的时候我们已经将这层节点放入队列是不是只需要判定一下for循环的索引值是否等于队列长度 - 1即可这样我们找到了最右边的节点同样的如果for循环的索引值 0 那么找到的就是这层最左边的节点。 function rightSideView(root) {const result [];let queue [root];if (!root) {return [];}while (queue.length 0) {const sizeOfQueue queue.length;for (let indexOfQueue 0; indexOfQueue sizeOfQueue; indexOfQueue) {const treeNode queue.shift();if (treeNode.left) {queue.push(treeNode.left);}if (treeNode.right) {queue.push(treeNode.right);}// 如果是队列的最后一个节点就是每一层最右边的节点if (indexOfQueue sizeOfQueue - 1) {result.push(treeNode.val);}}}return result;
}
总结
掌握了层序遍历的方法就可以对很多二叉树的变种题做出应对。
