剑指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 是不是为空执⾏第⼆步循环。javapublic class Solution { public ArrayList ArrayList Integer Print(TreeNode pRoot) { LinkedList TreeNode nodes new LinkedList (); ArrayList ArrayList Integer results new ArrayList(); boolean reverse true; if (pRoot ! null) { nodes.add(pRoot); while (!nodes.isEmpty()) { ArrayList Integer integers new ArrayList(); int size nodes.size(); for (int i 0; i size; i) { TreeNode node nodes.poll(); if (reverse) { integers.add(node.val); } else { integers.add(0, node.val); } if (node.left ! null) { nodes.offer(node.left); } if (node.right ! null) { nodes.offer(node.right); } } if (integers.size() ! 0) { results.add(integers); } reverse !reverse; } } return results; } }空间复杂度由于借助了额外的 list 为 O(n)时间复杂度由于每个节点进⼊队列⼜出来为 O(2n) 也是 O(n) 。队列 方向反转这是最直接的方法。我们进行标准的层序遍历但用一个标志位记录当前层是奇数层还是偶数层。对于偶数层我们在将该层的节点值列表加入最终结果前先进行反转javaimport java.util.*; public class Solution { public ArrayListArrayListInteger Print(TreeNode pRoot) { ArrayListArrayListInteger result new ArrayList(); if (pRoot null) return result; QueueTreeNode queue new LinkedList(); queue.offer(pRoot); boolean leftToRight true; // 方向标志true表示从左到右 while (!queue.isEmpty()) { int levelSize queue.size(); // 当前层的节点数 ArrayListInteger levelList new ArrayList(); // 遍历当前层的所有节点 for (int i 0; i levelSize; i) { TreeNode node queue.poll(); levelList.add(node.val); // 将节点值加入当前层列表 // 将下一层的节点按标准顺序先左后右加入队列 if (node.left ! null) queue.offer(node.left); if (node.right ! null) queue.offer(node.right); } // 如果是偶数层从第0层开始算则为奇数索引反转当前层列表 if (!leftToRight) { Collections.reverse(levelList); } result.add(levelList); leftToRight !leftToRight; // 切换方向 } return result; } }时间复杂度O(n)。每个节点被访问一次对于偶数层Collections.reverse的时间复杂度为 O(当前层节点数)所有层的节点数相加为 n因此总时间复杂度为 O(n)。空间复杂度O(n)。队列和结果列表所需空间与节点数 n 成线性关系。双栈交替利用栈后进先出LIFO的特性来自然地实现顺序的反转。我们使用两个栈一个用于处理当前层另一个用于存储下一层的节点javaimport java.util.*; public class Solution { public ArrayListArrayListInteger Print(TreeNode pRoot) { ArrayListArrayListInteger result new ArrayList(); if (pRoot null) return result; StackTreeNode stack1 new Stack(); // 处理奇数层从左到右 StackTreeNode stack2 new Stack(); // 处理偶数层从右到左 stack1.push(pRoot); // 当两个栈都为空时遍历结束 while (!stack1.isEmpty() || !stack2.isEmpty()) { ArrayListInteger levelList new ArrayList(); if (!stack1.isEmpty()) { // 处理stack1奇数层其子节点将以“从右到左”的顺序压入stack2 while (!stack1.isEmpty()) { TreeNode node stack1.pop(); levelList.add(node.val); // 关键先左子节点后右子节点入栈出栈顺序则为先右后左 if (node.left ! null) stack2.push(node.left); if (node.right ! null) stack2.push(node.right); } } else { // 处理stack2偶数层其子节点将以“从左到右”的顺序压入stack1 while (!stack2.isEmpty()) { TreeNode node stack2.pop(); levelList.add(node.val); // 关键先右子节点后左子节点入栈出栈顺序则为先左后右 if (node.right ! null) stack1.push(node.right); if (node.left ! null) stack1.push(node.left); } } result.add(levelList); } return result; }