乐趣区

关于leetcode:JavaScript刷LeetCode拿offer二叉树层序遍历篇

jiezi

前言

博主最近在刷leetcode，做到二叉树套题的时候发现很多题的解题思路都是基于二叉树的层序遍从来实现的，因而写下这篇文章，记录一下二叉树层序遍历这件 ” 神器 ” 在实战的使用。

[leetcode] 102. 二叉树的层序遍历

二叉树的层序遍历与传统的前序、中序、后序遍历都有一些区别，他是按层级、从左到右、从上到下进行遍历的，因而当我在遍历以后层节点的时候，必定须要记录以后层所有节点的left、right，保留到队列中，进行下一轮遍历，直到节点没有left、right，则代表曾经遍历到了最初一层了。

因而须要借助一个辅助数据结构——队列 ，队列先进后出，合乎层序遍历的程序性，其实此题就是 队列 + 广度优先遍历 的一道联合题。

间接看代码吧：

/** * 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) {const res = [], queue = [];
    queue.push(root);
    if(root === null) return res;

    while(queue.length !== 0) {let level = [];
        const length = queue.length
        for(var i = 0; i < length; i++) {var node = queue.shift();
            level.push(node.val);
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
        res.push(level);
    }
    return res;
};

接下来咱们逐行剖析代码。

  • 首先定义了一个后果和一个队列，对应 res 和queue，将顶层的 root 节点退出到队列中，开启循环。
  • 在每一轮 while 循环中，咱们从左到右顺次取出节点(shift api) 并且判断每个节点下一层是否有后辈 (left、right) 的判断，如果有，则退出到队列中。
  • const length = queue.length记录了队列在每一层遍历开始时的最后状态，保障了前面的 for 循环遍历的内容是以后层的节点，不会因为 left、right 退出到队列中的节点影响到以后层的循环轮数。
  • 最终，队列中所有节点都遍历结束，在 for 循环中也没有发现新的上层节点，循环完结，返回后果。

此时咱们就把握了二叉树的层序遍历了，那么如下九道力扣上的题目，只须要批改模板的两三行代码（不能再多了），便可打倒！你真的会发现，了解了层序遍历后，解决这些关联题，会蛟龙得水个别简略

  • 102. 二叉树的层序遍历
  • 107. 二叉树的档次遍历 II
  • 199. 二叉树的右视图
  • 637. 二叉树的层平均值
  • 429.N 叉树的前序遍历
  • 515. 在每个树行中找最大值
  • 116. 填充每个节点的下一个右侧节点指针
  • 117. 填充每个节点的下一个右侧节点指针 II
  • 104. 二叉树的最大深度
  • 111. 二叉树的最小深度

[leetcode] 107. 二叉树的层序遍历 II

此题与 102. 二叉树的层序遍历 极其类似，只须要把最初的 res 后果的排列程序扭转一下即可，代码架构和 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 levelOrderBottom = function(root) {var res = [], queue = [];
    queue.push(root);
    if(root === null) return res;
    while(queue.length) {
        let length = queue.length;
        const level = [];
        for(var i = 0; i < length; i++) {var node = queue.shift();
            level.push(node.val)
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
        res.unshift(level);
    }
    return res;
};

参考视频：传送门

[leetcode] 199. 二叉树的右视图

此题从题目形容中能够看到，须要收集每一层的最初一个节点，有了 ” 神器 ” 的你，此时曾经有思路了吧？这不是只须要在每一轮 while 循环中的 for 里加一个判断条件，取出最初一个节点就好了？上代码！

代码:

/** * 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) {var res = [], queue = [];
    queue.push(root);
    if(root === null) return res;
    while(queue.length !== 0){
        const length = queue.length;
        for(var i = 0; i < length; i++) {var node = queue.shift();
            if(i === length - 1) {res.push(node.val);
            }
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
    }
    return res;
};

[leetcode] 637. 二叉树的层平均值

此题只须要在每层节点取完当前，对节点的平均值进行一个计算即可，相比于后面几题，区别在收集的返回后果不一样，解题代码架构没有区别。

代码:

/** * 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 averageOfLevels = function(root) {var res = [], queue = [];
    queue.push(root);
    if(root === null) return res;

    while(queue.length !== 0) {
        const length = queue.length;
        let total = 0;
        for(var i = 0; i < length; i++) {let node = queue.shift();
            total += node.val;
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
        res.push(total / length);
    }
    return res;
};

[leetcode] 429.N 叉树的层序遍历

此题会有一点小弯须要绕一下，首先数据结构不同，TreeNode节点是这样的：

/** * // Definition for a Node. * function Node(val,children) {*    this.val = val; *    this.children = children; *}; */

也就是说咱们在每一层节点的循环中，不是再去收集节点的 left、right 了，而是去遍历节点的 children，将children 中的节点退出到队列中。

代码:

/** * // Definition for a Node. * function Node(val,children) {*    this.val = val; *    this.children = children; *}; */

/** * @param {Node|null} root
 * @return {number[][]} */
var levelOrder = function(root) {var res = [], queue = [];
    queue.push(root);
    if(root === null) return res;

    while(queue.length !== 0) {var level = [];
        var length = queue.length;
        for(var i = 0; i < length; i++) {var node = queue.shift();
            level.push(node.val)
            for(var item of node.children) {item && queue.push(item);
            }
        }
        res.push(level);
    }
    return res;
};

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

此题相似于637. 二叉树的层平均值，只是每一层收集的内容变成了最大值。

代码:

/** * 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) {var res = [], queue = [];
    queue.push(root);
    if(root === null) return res;

    while(queue.length !== 0) {
        const length = queue.length;
        const list = [];
        for(var i = 0; i < length; i++) {var node = queue.shift();
            list.push(node.val);
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
        res.push(Math.max(...list));
    }
    return res;
};

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

此题无需从新组装新的返回内容，只须要重新组建 root 中的每一个节点即可，每一个 TreeNode 默认的 next 为null，依据题目要求，在每一层所有节点，咱们对除了最右节点以外的所有节点增加一个 next 属性即可，依据队列先进先出的准则，next的值就是queue[0]，也就是队列的首项。

代码:

/** * // 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) {var queue = [root];
    if(root === null) return root;
    while(queue.length) {
        const length = queue.length;
        for(var i = 0; i < length; i++) {var node = queue.shift();
            if(i < length - 1) {node.next = queue[0];
            }
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
    }
    return root;
};

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

此题与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 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;
};

[leetcode] 104. 二叉树的最大深度

此题比较简单，只须要在遍历的过程中一直记录 height 即可，当层序遍历完结，返回 height 就解决了。

/** * 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 maxDepth = function(root) {if(root === null) return root;
    var queue = [root];
    var height = 0;
    while(queue.length > 0) {
        const length = queue.length;
        height++;
        for(var i = 0; i < length; i++) {var node = queue.shift();
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
    }
    return height
};

[leetcode] 111. 二叉树的最小深度

此题与 104. 二叉树的最大深度 相似，区别在于须要提前结束循环，通过判断树节点是否满足 node.left === null && node.right === null，就能够晓得二叉树的最小深度是哪个节点，将该节点遍历时的height 返回即可。

代码:

/** * 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 root;
    var queue = [root];
    var height = 0;

    while(queue.length > 0) {
        const n = queue.length;
        height++;
        for(var i = 0; i < n; i++) {var node = queue.shift();
            if(node.left === null && node.right === null) {return height;}
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
    }
    return height;
};

结尾

二叉树的层序遍历实质上是 队列 + 广度优先遍历 的联合使用诞生进去的 ” 神器 ”，此时就会发现通过它能够解决 leetcode 中很多二叉树的题目！

退出移动版