剑指offer-59、按之字形顺序打印⼆叉树

题⽬描述

请实现⼀个函数按照之字形打印⼆叉树，即第⼀⾏按照从左到右的顺序打印，第⼆层按照从右⾄左的顺序打印，第三⾏按照从左到右的顺序打印，其他⾏以此类推。
示例1
输⼊：{8,6,10,5,7,9,11}
返回值：[[8],[10,6],[5,7,9,11]]
思路及解答

双向链表（推荐）

• 借助双向链表，初始化⼀个添加⽅向 boolean 值，先将根节点添加进去：
  
• 获取 list ⾥⾯剩下的元素的个数，挨个取出就是⼀层，取出的时候，如果 reverse 为 true ，则往链表的第 0 个索引位置添加，否则直接在后⾯添加，然后判断每⼀个取出来的节点的左右节点是不是为空，不为空则加⼊链表。
  
• 每⼀层处理完之后，将 list 加⼊结果集中，然后翻转 reverse 的值，继续判断 list 是不是为空，执⾏第⼆步循环。
  

1. public class Solution {
2.     public ArrayList < ArrayList < Integer >> Print(TreeNode pRoot) {
3.         LinkedList < TreeNode > nodes = new LinkedList < > ();
4.         ArrayList < ArrayList < Integer >> results = new ArrayList();
5.         boolean reverse = true;
6.         if (pRoot != null) {
7.             nodes.add(pRoot);
8.             while (!nodes.isEmpty()) {
9.                 ArrayList < Integer > integers = new ArrayList();
10.                 int size = nodes.size();
11.                 for (int i = 0; i < size; i++) {
12.                     TreeNode node = nodes.poll();
13.                     if (reverse) {
14.                         integers.add(node.val);
15.                     } else {
16.                         integers.add(0, node.val);
17.                     }
18.                     if (node.left != null) {
19.                         nodes.offer(node.left);
20.                     }
21.                     if (node.right != null) {
22.                         nodes.offer(node.right);
23.                     }
24.                 }
25.                 if (integers.size() != 0) {
26.                     results.add(integers);
27.                 }
28.                 reverse = !reverse;
29.             }
30.         }
31.         return results;
32.     }
33. }

复制代码

• 空间复杂度由于借助了额外的 list ，为 O(n)
  
• 时间复杂度，由于每个节点进⼊队列⼜出来，为 O(2n) ，也是 O(n) 。
  

队列 + 方向反转

这是最直接的方法。我们进行标准的层序遍历，但用一个标志位记录当前层是奇数层还是偶数层。对于偶数层，我们在将该层的节点值列表加入最终结果前，先进行反转

1. import java.util.*;
3. public class Solution {
4.     public ArrayList> Print(TreeNode pRoot) {
5.         ArrayList> result = new ArrayList<>();
6.         if (pRoot == null) return result;
8.         Queue<TreeNode> queue = new LinkedList<>();
9.         queue.offer(pRoot);
10.         boolean leftToRight = true; // 方向标志，true表示从左到右
12.         while (!queue.isEmpty()) {
13.             int levelSize = queue.size(); // 当前层的节点数
14.             ArrayList<Integer> levelList = new ArrayList<>();
16.             // 遍历当前层的所有节点
17.             for (int i = 0; i < levelSize; i++) {
18.                 TreeNode node = queue.poll();
19.                 levelList.add(node.val); // 将节点值加入当前层列表
21.                 // 将下一层的节点按标准顺序（先左后右）加入队列
22.                 if (node.left != null) queue.offer(node.left);
23.                 if (node.right != null) queue.offer(node.right);
24.             }
26.             // 如果是偶数层（从第0层开始算则为奇数索引），反转当前层列表
27.             if (!leftToRight) {
28.                 Collections.reverse(levelList);
29.             }
30.             result.add(levelList);
31.             leftToRight = !leftToRight; // 切换方向
32.         }
33.         return result;
34.     }
35. }

复制代码

• 时间复杂度：O(n)。每个节点被访问一次，对于偶数层，Collections.reverse的时间复杂度为 O(当前层节点数)，所有层的节点数相加为 n，因此总时间复杂度为 O(n)。
  
• 空间复杂度：O(n)。队列和结果列表所需空间与节点数 n 成线性关系。
  

双栈交替

利用栈后进先出（LIFO）的特性来自然地实现顺序的反转。我们使用两个栈，一个用于处理当前层，另一个用于存储下一层的节点

1. import java.util.*;
3. public class Solution {
4.     public ArrayList> Print(TreeNode pRoot) {
5.         ArrayList> result = new ArrayList<>();
6.         if (pRoot == null) return result;
8.         Stack<TreeNode> stack1 = new Stack<>(); // 处理奇数层（从左到右）
9.         Stack<TreeNode> stack2 = new Stack<>(); // 处理偶数层（从右到左）
10.         stack1.push(pRoot);
12.         // 当两个栈都为空时，遍历结束
13.         while (!stack1.isEmpty() || !stack2.isEmpty()) {
14.             ArrayList<Integer> levelList = new ArrayList<>();
16.             if (!stack1.isEmpty()) {
17.                 // 处理stack1（奇数层），其子节点将以“从右到左”的顺序压入stack2
18.                 while (!stack1.isEmpty()) {
19.                     TreeNode node = stack1.pop();
20.                     levelList.add(node.val);
21.                     // 关键：先左子节点后右子节点入栈，出栈顺序则为先右后左
22.                     if (node.left != null) stack2.push(node.left);
23.                     if (node.right != null) stack2.push(node.right);
24.                 }
25.             } else {
26.                 // 处理stack2（偶数层），其子节点将以“从左到右”的顺序压入stack1
27.                 while (!stack2.isEmpty()) {
28.                     TreeNode node = stack2.pop();
29.                     levelList.add(node.val);
30.                     // 关键：先右子节点后左子节点入栈，出栈顺序则为先左后右
31.                     if (node.right != null) stack1.push(node.right);
32.                     if (node.left != null) stack1.push(node.left);
33.                 }
34.             }
35.             result.add(levelList);
36.         }
37.         return result;
38.     }
39. }

复制代码

• 时间复杂度：O(n)。每个节点被压入栈和弹出栈各一次。
  
• 空间复杂度：O(n)。两个栈在最坏情况下共同存储 n 个节点。
  

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！