二叉树 - 二叉树的层序遍历

本文主要是介绍二叉树 - 二叉树的层序遍历，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

二叉树的层序遍历

102. 二叉树的层序遍历

/*** 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 levelOrder = function (root) {// 二叉树的层序遍历let res = [], queue = [];queue.push(root);if (root === null) {return res;}while (queue.length !== 0) {// 记录当前层级节点数let length = queue.length;// 存放每一层的节点let curLevel = [];for (let i = 0; i < length; i++) {let node = queue.shift();curLevel.push(node.val);// 存放当前层下一层的节点node.left && queue.push(node.left);node.right && queue.push(node.right);}// 把每一层的结果放到结果数组res.push(curLevel);}return res;
}

107. 二叉树的层序遍历 II

/*** 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) {let res = [], queue = [];queue.push(root);while (queue.length && root !== null) {// 存放当前层级节点数组let curLevel = [];// 计算当前层级节点数量let length = queue.length;while (length--) {let node = queue.shift();// 把当前层节点存入curLevel数组curLevel.push(node.val);// 把下一层级的左右节点存入queue队列node.left && queue.push(node.left);node.right && queue.push(node.right);}//  从数组前头插入值，避免最后反转数组，减少运算时间res.unshift(curLevel);}return res;
}

199. 二叉树的右视图

/*** 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 rightSideView = function (root) {// 二叉树右视图 只需要把每一层最后一个节点存储到res数组let res = [], queue = [];queue.push(root);while (queue.length && root !== null) {// 记录当前层级节点个数let length = queue.length;while (length--) {let node = queue.shift();// length长度为0的时候表明到了层级最后一个节点if (!length) {res.push(node.val);}node.left && queue.push(node.left);node.right && queue.push(node.right);}}return res;
};

637. 二叉树的层平均值

var averageOfLevels = function (root) {let res = [], queue = [];queue.push(root);while (queue.length) {// 每一层节点个数let lengthLevel = queue.length,len = queue.length,// sum记录每一层的和sum = 0;while (lengthLevel--) {const node = queue.shift();sum += node.val;// 队列存放下一层节点node.left && queue.push(node.left);node.right && queue.push(node.right);}// 求平均值res.push(sum / len);    }return res;
};

429. N叉树的层序遍历

/*** // Definition for a _Node.* function _Node(val,children) {*    this.val = val;*    this.children = children;* };*//*** @param {_Node|null} root* @return {number[][]}*/
var levelOrder = function (root) {// 每一层可能有两个以上，所以不再使用node.left node.rightlet res = [], queue = [];queue.push(root);while (queue.length && root !== null) {// 记录每一层节点个数还是和二叉树一致let length = queue.length;// 存放每层节点 也和二叉树一致let curLevel = [];while (length--) {let node = queue.shift();curLevel.push(node.val);// 这里不再是 node.left node.right 而是循环node.childrenfor (let item of node.children) {item && queue.push(item);}}res.push(curLevel);}return res;
};

515. 在每个树行中找最大值

/*** 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 largestValues = function (root) {let res = [], queue = [];queue.push(root);if (root === null) {return res;}while (queue.length) {let lengthLevel = queue.length,// 初始值设为负无穷大max = -Infinity;while (lengthLevel--) {const node = queue.shift();// 在当前层中找到最大值max = Math.max(max, node.val);// 找到下一层的节点node.left && queue.push(node.left);node.right && queue.push(node.right);}res.push(max);}return res;
}

116. 填充每个节点的下一个右侧节点指针

/*** // Definition for a _Node.* function _Node(val, left, right, next) {*    this.val = val === undefined ? null : val;*    this.left = left === undefined ? null : left;*    this.right = right === undefined ? null : right;*    this.next = next === undefined ? null : next;* };*//*** @param {_Node} root* @return {_Node}*/
var connect = function (root) {if (root === null) {return root;}let queue = [root];while (queue.length) {let n = queue.length;for (let i = 0; i < n; i++) {let node = queue.shift();if (i < n - 1) {node.next = queue[0];}node.left && queue.push(node.left);node.right && queue.push(node.right);}}return root;
}

117. 填充每个节点的下一个右侧节点指针 II

/*** // Definition for a _Node.* function _Node(val, left, right, next) {*    this.val = val === undefined ? null : val;*    this.left = left === undefined ? null : left;*    this.right = right === undefined ? null : right;*    this.next = next === undefined ? null : next;* };*//*** @param {_Node} root* @return {_Node}*/
var connect = function (root) {if (root === null) {return null;}let queue = [root];while (queue.length > 0) {let n = queue.length;for (let i = 0; i < n; i++) {let node = queue.shift();if (i < n - 1) node.next = queue[0];if (node.left !== null) queue.push(node.left);if (node.right !== null) queue.push(node.right);}}return root;
};

104. 二叉树的最大深度

var maxDepth = function (root) {// 二叉树的 最大深度 是指从根节点到最远叶子结点的最长路径上的节点数// 叶子节点是指没有子节点的节点let max = 0, queue = [root];if (root === null) {return max;}while (queue.length) {max++;let length = queue.length;while (length--) {let node = queue.shift();node.left && queue.push(node.left);node.right && queue.push(node.right);}}return max;
};

111. 二叉树的最小深度

/*** 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 minDepth = function (root) {if (root === null) return 0;let queue = [root];let depth = 0;while (queue.length) {let n = queue.length;depth++;for (let i = 0; i < n; i++) {let node = queue.shift();// 如果左右节点都是null（在遇见的第一个leaf节点上），则该节点深度最小if (node.left === null && node.right === null) {return depth;}node.left && queue.push(node.left);node.right && queue.push(node.right);}}return depth;
};

这篇关于二叉树 - 二叉树的层序遍历的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---