二叉树层序遍历¶

统计信息：字数 4065 阅读9分钟

二叉树的层序遍历本是下一章的内容，但是其中队列的性质又体现得太明显，因此就以这样一类问题来让大家练习队列的相关操作。这里会不仅仅涉及到普通的层序遍历, 而且涉及到变形问题，让大家彻底掌握。

普通的层次遍历¶

给定一个二叉树，返回其按层次遍历的节点值。（即逐层地，从左到右访问所有节点）。

示例:

结果应输出:

[
  [3],
  [9,20],
  [15,7]
]

来源: LeetCode第102题

实现¶

    /**
     * @param {TreeNode} root
     * @return {number[][]}
     */
    var levelOrder = function(root) {
        if(!root) return [];
        let queue = [];
        let res = [];
        let level = 0;
        queue.push(root);
        let temp;
        while(queue.length) {
            res.push([]);
            let size = queue.length;
            // 注意一下: size -- 在层次遍历中是一个非常重要的技巧
            while(size --) {
                // 出队
                let front = queue.shift();
                res[level].push(front.val);
                // 入队
                if(front.left) queue.push(front.left);
                if(front.right) queue.push(front.right);
            }        
            level++;
        }
        return res;
    };

二叉树的锯齿形层次遍历¶

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：

给定二叉树 [3,9,20,null,null,15,7], 输出应如下:

返回锯齿形层次遍历如下：

[
  [3],
  [20,9],
  [15,7]
]

来源: LeetCode第103题

思路¶

这一题思路稍微不同，但如果把握住层次遍历的思路，就会非常简单。

代码实现¶

    var zigzagLevelOrder = function(root) {
        if(!root) return [];
        let queue = [];
        let res = [];
        let level = 0;
        queue.push(root);
        let temp;
        while(queue.length) {
            res.push([]);
            let size = queue.length;
            while(size --) {
                // 出队
                let front = queue.shift();
                res[level].push(front.val);
                if(front.left) queue.push(front.left);
                if(front.right) queue.push(front.right);
            }  
            // 仅仅增加下面一行代码即可
            if(level % 2) res[level].reverse();      
            level++;
        }
        return res;
    };

二叉树的右视图¶

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例:

输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

来源: LeetCode第199题

思路¶

右视图？如果你以 DFS 即深度优先搜索的思路来想，你会感觉异常的痛苦。没错，当初我就是这样被坑的:）

但如果用广度优先搜索的思想，即用层序遍历的方式，求解这道题目也变得轻而易举。

代码实现¶

    /**
     * @param {TreeNode} root
     * @return {number[]}
     */
    var rightSideView = function(root) {
        if(!root) return [];
        let queue = [];
        let res = [];
        queue.push(root);
        while(queue.length) {
            res.push(queue[0].val);
            let size = queue.length;
            while(size --) {
                // 一个size的循环就是一层的遍历，在这一层只拿最右边的结点
                let front = queue.shift();
                if(front.right) queue.push(front.right);
                if(front.left) queue.push(front.left);
            }
        }
        return res;
    };

Last update: November 9, 2024