层次遍历

一.什么是层次遍历

层次遍历就是广度优先,如图中步骤:

1. 首先3入队。
2. 然后3出队,之后将3的左右子孩子9和20 保存到队列中。
3. 之后9出队,将9的左右子孩子8和13入队。
4. 之后20出队,将20的左右子孩子15和7入队。
5. 之后 8,13,15,7分别出队,此时都是叶子结点,只出队就行了

image

    3
   / \
  9  20
    /  \
   15   7

层序遍历后输出:

 public static List<Integer> simpleLevelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        //定义存储数组
        List<Integer> res = new ArrayList<>();
        //定义队列
        LinkedList<TreeNode> queue = new LinkedList<>();
        //此时队列为空,将根节点加入队列
        queue.add(root);
        while (!queue.isEmpty()) {
            //每次循环移除队列的第一个元素
            TreeNode node = queue.remove();
            res.add(node.val);
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        return res;
}
}

核心思想就是,每次队列中出一个父节点,如何进对应数量的子节点

最后结束时,当队列中只剩叶子节点时,就会继续循环遍历最后的叶子节点加入数组,然后结束

队列在这道题充当缓存的作用,但是如果将每一层的节点分开应该怎么做呢?看下面这题

二.基本层序遍历

1.L102

LeetCode102 题目要求:给你一个二叉树,请你返回其按层序遍历得到的节点值。(即逐层地,从左到右访问所有节点)。

输入:root = [3,9,20,null,null,15,7]
输出:[[3],[9,20],[15,7]]
示例 2:

输入:root = [1]
输出:[[1]]
示例 3:

输入:root = []
输出:[]

这道题和上题思路基本相同,唯一不同的是循环的方式不一样,通过for循环记录每一层需要记录子节点的次数,1,2,4,8;因为在上一道题中,queue内的size变化始终是大于0的,因此我们需要将长度在循环外记录,执行size次(也就是当前层的父节点的数量)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
  if (root == null) {
            return new ArrayList<>();
        }
        //定义存储数组
        List<List<Integer>>res = new ArrayList<>();
        //定义队列
        LinkedList<TreeNode> queue = new LinkedList<>();
        //此时队列为空,将根节点加入队列
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer>tem = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.remove();
                tem.add(node.val);

                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            res.add(tem);


        }
        return res;
    }
}

2.L107

给你二叉树的根节点 root ,返回其节点值 自底向上的层序遍历 。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)

image-20231211092129679

遍历完一层节点之后,将存储该层节点值的列表添加到结果列表的尾部。

本题唯一需要关注的一点是可以借助链表的特性来减少添加节点时的一点时间复杂度

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
if (root == null) {
            return new ArrayList<>();
        }
        Queue<TreeNode> queue = new LinkedList<>();
        LinkedList<List<Integer>> res = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            
            int size = queue.size();
            List<Integer>tem = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                TreeNode treeNode = queue.remove();
                tem.add(treeNode.val);
                if (treeNode.left != null) {
                    queue.add(treeNode.left);
                }
                if (treeNode.right != null) {
                    queue.add(treeNode.right);
                }
            }
            res.add(0,tem);

        }
return res;
    }
}

此处补充一下Java中集合中队列与链表的关系

链表中添加可以使用索引0,表示从左边开始添加,移除元素可以不使用参数

3.L103

LeetCode103 题,要求是:给定一个二叉树,返回其节点值的锯齿形层序遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
例如:给定二叉树 [3,9,20,null,null,15,7]

image-20231213122119666

本题与107不同的是:

1.107翻转的是某一层的集合,而本题翻转的是某一层中的元素,利用双向队列,添加元素时决定从左往右或从右边往左

2.使用布尔值标记翻转,加快运算速度

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        boolean flag = true;
        while (!queue.isEmpty()) {
            int size = queue.size();

            Deque<Integer> tem = new LinkedList<>();

            for (int i = 0; i < size; i++) {
                TreeNode polled = queue.poll();
                //这里判断从左还是从右边添加
                if (flag){
                    tem.addLast(polled.val);
                }else {
                    tem.addFirst(polled.val);
                }
                TreeNode right = polled.right, left = polled.left;
                if (left != null) {
                    queue.add(left);
                }
                if (right != null) {
                    queue.add(right);
                }
            }
            res.add(new LinkedList<>(tem));
            flag=!flag;
        }
        return res;
    }

4.L429

LeetCode429 给定一个 N 叉树,返回其节点值的层序遍历。(即从左到右,逐层遍历)。
树的序列化输入是用层序遍历,每组子节点都由 null 值分隔(参见示例)。

image-20231214093850324

输入:root = [1,null,3,2,4,null,5,6](表述树的元素是这个序列)
输出:[[1],[3,2,4],[5,6]]

N叉树的定义如下,就是一个值,加一个列表,其类型仍然是Node:

class Node {
    public int val;
    public List<Node> children;
}

本题思路:最外层循环负责整个树,第二层负责每一层,最内层循环负责将每个节点加入到队列中

因此可以第二层循环记录当前层的节点数量,最内层对节点的子节点集合进行遍历加入到队列中

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
    
   List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Deque<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            List<Integer> tem = new LinkedList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Node poll = queue.poll();
                tem.add(poll.val);
                for (Node child : poll.children) {
                    if (child != null) queue.add(child);
                }
            }
            res.add(tem);


        }
        return res;
    }
}

另一种写法是第二层不使用size,通过while循环,遍历完一层时,将当前的节点切换为当前遍历的节点

这种做法通过在遍历每一层节点时定义一个队列添加下一层所有节点,因此当最内层循环结束的时候,第二层也会结束,此时将queue队列换成刚刚最内层循环添加的一层所有的节点,此时循环继续

两个方法相同思想都是将某一层的节点全部加入到队列当中

 public static List<List<Integer>> nLevelOrder(NTreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Deque<NTreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Deque<NTreeNode> next = new ArrayDeque<>();
            List<Integer> tem = new LinkedList<>();
            while (!queue.isEmpty()) {

                NTreeNode poll = queue.poll();
                tem.add(poll.val);
                for (NTreeNode child : poll.children) {
                    if (child != null) next.add(child);
                }
            }
            queue=next;
            res.add(tem);


        }
        return res;
 }

三.几个处理元素的题目

L515

给定一棵二叉树的根节点 root ,请找出该二叉树中每一层的最大值。

方法一:最大值通过集合stream寻找(记得import)Optional类,||| 恭喜您击败了1.69%

 import java.util.Optional;
class Solution {
    public List<Integer> largestValues(TreeNode root) {
  List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        res.add(root.val);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode polled = queue.remove();
                TreeNode left = polled.left;
                TreeNode right = polled.right;
                if (left != null) queue.add(left);
                if (right != null) queue.add(right);
            }
            if (!queue.isEmpty()) {
                Optional<TreeNode> max = queue.stream().max(Comparator.comparingInt(a -> a.val));
                res.add(max.get().val);
            }
        }
        return res;
    }
}

方法二:变量记录,因为题目要求节点的值数字有要求,因此使用最小值

  • 二叉树的节点个数的范围是 [0,104]
  • -231 <= Node.val <= 231 - 1
class Solution {
    public List<Integer> largestValues(TreeNode root) {

        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
   
        while (!queue.isEmpty()) {
            int size = queue.size();
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < size; i++) {
                TreeNode polled = queue.remove();
                max = Math.max(polled.val, max);
                TreeNode left = polled.left;
                TreeNode right = polled.right;
                if (left != null) queue.add(left);
                if (right != null) queue.add(right);
            }
  res.add(max);
        }
        return res;
    }
}

方法三:DFS

L637

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

image-20231215095955405

题解:和上题思路相同,每一层在从队列弹出时累加,最终求出平均值

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
     List<Double> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> list = new LinkedList<>();
        list.add(root);
        while (!list.isEmpty()) {
            int size = list.size();
            double sum = 0;
            for (int i = 0; i < size; i++) {
                TreeNode polled = list.remove();
                sum += polled.val;
                TreeNode left = polled.left;
                TreeNode right = polled.right;
                if (left != null) list.add(left);
                if (right != null) list.add(right);
            }
            res.add((double) (sum/size));
        }
        return res;
    }
}

L199 二叉树的右视图

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

image-20231219091436144

示例1:
输入: root = [2,1,3]
输出: 1

示例2:
输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7

这道题的思路依然是遍历每一层,然后取到每层最后一个节点的值就行

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
 List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode>queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()){
           
            int size = queue.size();
            TreeNode tem = null;
            for (int i = 0; i <size; i++) {
                 tem=  queue.remove();
            
                TreeNode left = tem.left;
                TreeNode right = tem.right;
                if (left!=null){
                    queue.add(left);
                }
                if (right!=null){
                    queue.add(right);
                }
            }
               res .add(tem.val);
            }
return res;

          
    }
}

L513 最底层最左边

上面这个层次遍历的思想可以方便的解决LeetCode513. 二叉树最底层最左边的值的问题:给定一个二叉树的 根节点root,请找出该二叉树的 最底层 最左边 节点的值。

image-20231220000243183

假设二叉树中至少有一个节点。

示例1:
输入: root = [2,1,3]
输出: 1

示例2:
输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7

这道题第一个思路一定是依次遍历每一层,然后取每一层的第一个进行记录,但是这样做会很复杂,我们可以很快想到最开始的方法:

逐一遍历但是这样会造成一个问题是我们始终只能得到最右边的节点是最后一个,我们无法知道什么时候结束,但是这个时候,我们想到前面有道题翻转某一层节点(103),这两种结合起来不就是最优解吗?

换句话说,队列中存放的时候,只需要从右边开始存放即可

class Solution {
    public int findBottomLeftValue(TreeNode root) {

     if (root.left == null && root.right == null) {
            return root.val;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        TreeNode node = null;
        while (!queue.isEmpty()) {
            node = queue.remove();
            TreeNode right = node.right, left = node.left;

            if (right != null) {
                // 先把右节点加入 queue
                queue.offer(node.right);
            }
            if (left != null) {
                // 再把左节点加入 queue
                queue.offer(node.left);
            }
        }

        return node.val;
        
    }
}