题目描述

题目一

image.png
层序遍历即可

  1. class Solution {
  2.     /**
  3.         * 广度优先遍历
  4.         *
  5.         * @param root
  6.         * @return
  7.         */
  8.     public int[] levelOrder(TreeNode root) {
  9.         if (root == null) {
  10.             return new int[0];
  11.         }
  13.         List<Integer> list = new ArrayList<>();
  14.         Queue<TreeNode> queue = new LinkedList<>();
  15.         queue.offer(root);
  16.         while (!queue.isEmpty()) {
  17.             int len = queue.size();
  18.             while (len > 0) {
  19.                 TreeNode node = queue.poll();
  20.                 list.add(node.val);
  21.                 if (node.left != null) queue.offer(node.left);
  22.                 if (node.right != null) queue.offer(node.right);
  23.                 len--;
  24.             }
  25.         }
  26.         int[] res = new int[list.size()];
  27.         for (int i = 0; i < res.length; i++) {
  28.             res[i] = list.get(i);
  29.         }
  31.         return res;
  32.     }
  33. }

题目二

image.png
也是层序遍历

  1. class Solution {
  2.     public List<List<Integer>> levelOrder(TreeNode root) {
  3.         if (root == null) {
  4.             return new ArrayList<>();
  5.         }
  7.         List<List<Integer>> list = new ArrayList<>();
  8.         Queue<TreeNode> queue = new LinkedList<>();
  9.         queue.add(root);
  10.         while (!queue.isEmpty()) {
  11.             int len = queue.size();
  12.             List<Integer> list1 = new ArrayList<>();
  13.             while (len > 0) {
  14.                 TreeNode node = queue.poll();
  15.                 list1.add(node.val);
  16.                 if (node.left != null) queue.offer(node.left);
  17.                 if (node.right != null) queue.offer(node.right);
  18.                 len--;
  19.             }
  20.             list.add(list1);
  21.         }
  22.         return list;
  23.     }
  24. }

题目三

image.png

层序遍历 + 双端队列：

  • 利用双端队列的两端皆可添加元素的特性，设打印列表（双端队列） tmp ，并规定：

    • 奇数层 则添加至 tmp 尾部 ，

    • 偶数层 则添加至 tmp 头部 。

      1. /**
      2.    * 双端队列
      3.    *
      4.    * @param root
      5.    * @return
      6.    */
      7. public List<List<Integer>> levelOrder(TreeNode root) {
      8.    if (root == null) {
      9.        return new ArrayList<>();
      10.    }
      12.    List<List<Integer>> list = new ArrayList<>();
      13.    Queue<TreeNode> queue = new LinkedList<>();
      14.    int count = 1;
      15.    queue.add(root);
      16.    while (!queue.isEmpty()) {
      17.        int len = queue.size();
      18.        LinkedList<Integer> list1 = new LinkedList<>();
      19.        while (len > 0) {
      20.            TreeNode node = queue.poll();
      21.            if (count % 2 == 0) {
      22.                list1.addLast(node.val);
      23.            }else list1.addFirst(node.val);
      24.            if (node.left != null) queue.offer(node.left);
      25.            if (node.right != null) queue.offer(node.right);
      26.            len--;
      27.        }
      28.        count++;
      29.        list.add(list1);
      30.    }
      31.    return list;
      32. }

      层序遍历 + 倒序

      ```java /**

      • 反转解决 *
      • @param root
      • @return */ public List> levelOrder(TreeNode root) { if (root == null) { return new ArrayList<>(); }

      List> list = new ArrayList<>(); Queue queue = new LinkedList<>(); int count = 1; queue.add(root); while (!queue.isEmpty()) { int len = queue.size(); List list1 = new ArrayList<>(); while (len > 0) {

      1.    TreeNode node = queue.poll();
      2.    list1.add(node.val);
      3.    if (node.left != null) queue.offer(node.left);
      4.    if (node.right != null) queue.offer(node.right);
      5.    len--;

      } count++; // 表示奇数行还是偶数行 if (count % 2 == 1) Collections.reverse(list1); list.add(list1); } return list; }

```