题目地址(32 - III. 从上到下打印二叉树 III)

https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/

题目描述

  1. 请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
  5. 例如:
  6. 给定二叉树: [3,9,20,null,null,15,7],
  8.     3
  9.    / \
  10.   9  20
  11.     /  \
  12.    15   7
  15. 返回其层次遍历结果：
  17. [
  18.   [3],
  19.   [20,9],
  20.   [15,7]
  21. ]
  26. 提示：
  28. 节点总数 <= 1000

前置知识


公司

  • 暂无

思路

二叉树的层序遍历的基础上完成这道题 有两个方法 其中判断是不是偶数层就使用返回值数组的size判断

  1. 先将数据加入temp 然后在奇数层翻转数组
  2. temp由ArrayList改成linkedlist 双向链表 在每次向temp添加值的时候 先判断奇数层还是偶数层 奇数层就每次都把数据加到temp前面 偶数层相反

    关键点


代码

  • 语言支持：Java

Java Code:
方法1

  1. class Solution {
  2.     public List<List<Integer>> levelOrder(TreeNode root) {
  3.         ArrayList<List<Integer>> res = new ArrayList<>();
  4.         LinkedList<TreeNode> queue = new LinkedList<>();
  5.         if (root == null) {
  6.             return res;
  7.         }
  8.         queue.add(root);
  9.         while (!queue.isEmpty()) {
  10.             ArrayList<Integer> temp = new ArrayList<>();
  11.             int size = queue.size();
  12.             while (size > 0) {
  13.                 TreeNode poll = queue.poll();
  14.                 temp.add(poll.val);
  15.                 if (poll.left != null) {
  16.                     queue.add(poll.left);
  17.                 }
  18.                 if (poll.right != null) {
  19.                     queue.add(poll.right);
  20.                 }
  21.                 size--;
  22.             }
  23.             if (res.size() % 2 != 0) {
  24.                 Collections.reverse(temp);
  25.             }
  26.             res.add(temp);
  27.         }
  28.         return res;
  29.     }
  30. }

方法2

  1. class Solution {
  2.     public List<List<Integer>> levelOrder(TreeNode root) {
  3.         ArrayList<List<Integer>> res = new ArrayList<>();
  4.         LinkedList<TreeNode> queue = new LinkedList<>();
  5.         if (root == null) {
  6.             return res;
  7.         }
  8.         queue.add(root);
  9.         while (!queue.isEmpty()) {
  10.             LinkedList<Integer> temp = new LinkedList<>();
  11.             int size = queue.size();
  12.             while (size > 0) {
  13.                 TreeNode poll = queue.poll();
  14.                 if (res.size() % 2 == 0) {
  15.                     temp.add(poll.val);
  16.                 }else {
  17.                     temp.addFirst(poll.val);
  18.                 }
  20.                 if (poll.left != null) {
  21.                     queue.add(poll.left);
  22.                 }
  23.                 if (poll.right != null) {
  24.                     queue.add(poll.right);
  25.                 }
  26.                 size--;
  27.             }
  28.             res.add(temp);
  29.         }
  30.         return res;
  31.     }
  32. }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：剑指 Offer 32 - III. 从上到下打印二叉树 III 2 - 图1#card=math&code=O%28n%29&id=GnnZD)
  • 空间复杂度：剑指 Offer 32 - III. 从上到下打印二叉树 III 2 - 图2#card=math&code=O%28n%29&id=toPbc)