算法通关村第六关——原来如此简单

层次遍历：又叫广度优先遍历。就是从根节点开始，先访问根节点下面一层全部元素，再访问之后的层次，直到访问完二叉树的最后一层。

我们先看一下基础的层次遍历题，力扣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;
}

总结

掌握了层序遍历的方法，就可以对很多二叉树的变种题做出应对。