|
| 1 | +```text |
| 2 | +题目: 给定一个二叉树,返回其节点值的锯齿形层次遍历; |
| 3 | + (即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行) |
| 4 | +1.BFS(广度优先遍历): |
| 5 | + [1]思路: 从左到右遍历添加,再从右到左遍历添加,再从左到右遍历添加,以此类推 |
| 6 | + (1)使用双端队列保存每层的节点,在最后添加一个null,作为该层遍历完的标识; |
| 7 | + (2)原本是要更改节点放到队列中的位置,来实现从左到右再从右到左,但遍历每个节点时都要考虑其两子节点的位置太麻烦了 |
| 8 | + (3)简化: 控制<添加当前节点的左右子节点>的位置 -> 控制<添加节点值>的位置 |
| 9 | + (4)使用一个布尔变量保存遍历的方向,当遍历到null时,说明该层结束就需要变更方向 |
| 10 | + [2]实现: |
| 11 | + class Solution { |
| 12 | + public List<List<Integer>> zigzagLevelOrder(TreeNode root) { |
| 13 | + // 对节点进行判空 |
| 14 | + if (root == null) { |
| 15 | + return new ArrayList<>(); |
| 16 | + } |
| 17 | + // 定义一个结果集合 |
| 18 | + List<List<Integer>> results = new ArrayList<>(); |
| 19 | + // 定义一个LinkedList做双端队列用来保存节点(节点的添加依旧是从左到右) |
| 20 | + LinkedList<TreeNode> nodeQueue = new LinkedList<>(); |
| 21 | + // 向栈中添加初始节点(根节点与null) |
| 22 | + nodeQueue.addLast(root); |
| 23 | + // null用来表示当前层遍历结束(该层遍历结束后可做一些操作,如添加遍历结果到最终结果集,更改遍历方向等) |
| 24 | + nodeQueue.addLast(null); |
| 25 | + // 定义一个变量保存遍历方向(初始方向是从左到右即正向) |
| 26 | + boolean isLtoR = true; |
| 27 | + // 定义一个LinkedList用来保存每一层的值 |
| 28 | + LinkedList<Integer> levelList = new LinkedList<>(); |
| 29 | + // 遍历树 |
| 30 | + while (nodeQueue.size() > 0) { |
| 31 | + // 从双端队列中吐出头部节点 |
| 32 | + TreeNode curr = nodeQueue.pollFirst(); |
| 33 | + if (curr != null) { |
| 34 | + if (isLtoR) { |
| 35 | + // 当前层是正向则添加到尾部(右边) |
| 36 | + levelList.addLast(curr.val); |
| 37 | + } else { |
| 38 | + // 当前层是反向则添加到头部(左边) |
| 39 | + levelList.addFirst(curr.val); |
| 40 | + } |
| 41 | + // 将当前节点的不为null的子节点添加到节点集合 |
| 42 | + if (curr.left != null) { |
| 43 | + nodeQueue.addLast(curr.left); |
| 44 | + } |
| 45 | + if (curr.right != null) { |
| 46 | + nodeQueue.addLast(curr.right); |
| 47 | + } |
| 48 | + } else { |
| 49 | + // 进入此处说明该层已遍历结束,需要做的处理有: |
| 50 | + // 保存该层结果到结果集、添加下一层的结束标志、更改遍历方向 |
| 51 | + results.add(levelList); |
| 52 | + levelList = new LinkedList<>(); |
| 53 | + if (nodeQueue.size() > 0) { |
| 54 | + nodeQueue.addLast(null); |
| 55 | + } |
| 56 | + isLtoR = !isLtoR; |
| 57 | + } |
| 58 | + } |
| 59 | + return results; |
| 60 | + } |
| 61 | + } |
| 62 | + class TreeNode { |
| 63 | + int val; |
| 64 | + TreeNode left; |
| 65 | + TreeNode right; |
| 66 | + TreeNode(int x) { |
| 67 | + val = x; |
| 68 | + } |
| 69 | + } |
| 70 | + [3]复杂度分析: |
| 71 | + (1)时间复杂度: O(N),其中N是树中节点的数量,每个节点仅访问一次,双端队列的插入操作为常数时间,即最后为O(N) |
| 72 | + (2)空间复杂度: O(N),其中N是树中节点的数量 |
| 73 | + 除了输出数组,主要的内存开销是双端队列,任何时刻,队列中最多只存储两层节点;因此其大小不超过2L(L是一层的最大节点数); |
| 74 | + 包含最多节点的层可能是完全二叉树的叶节点层,大约有L=N/2个节点,因此最坏情况下,空间复杂度为2*N/2=N; |
| 75 | +``` |
0 commit comments