题目描述（中等难度）

103. Binary Tree Zigzag Level Order Traversal - 图1

和 102 题 类似，二叉树的层次遍历。只不过这题要求，第 1 层从左到右，第 2 层从右到左，第 3 层从左到右，第 4 层从右到左，交替进行。

思路分析

大家可以先做下 102 题 吧，直接在 102 题的基础上进行修改即可。从左到右和从右到左交替，所以我们只需要判断当前的 level，层数从 0 开始的话，偶数就把元素添加到当前层的末尾，奇数的话，每次把新元素添加到头部，这样就实现了从右到左的遍历。

解法一 DFS

判断 level 是偶数还是奇数即可。

  1. public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
  2.     List<List<Integer>> ans = new ArrayList<>();
  3.     DFS(root, 0, ans);
  4.     return ans;
  5. }
  7. private void DFS(TreeNode root, int level, List<List<Integer>> ans) {
  8.     if (root == null) {
  9.         return;
  10.     }
  11.     if (ans.size() <= level) {
  12.         ans.add(new ArrayList<>());
  13.     }
  14.     if ((level % 2) == 0) {
  15.         ans.get(level).add(root.val); //添加到末尾
  16.     } else {
  17.         ans.get(level).add(0, root.val); //添加到头部
  18.     }
  20.     DFS(root.left, level + 1, ans);
  21.     DFS(root.right, level + 1, ans);
  22. }

解法二 BFS 队列

如果是顺序刷题，前边的 97 题， 98 题，101 题，都用到了 BFS ，应该很熟悉了。

之前我们用一个 while 循环，不停的从队列中拿一个节点，并且在循环中将当前取出来的节点的左孩子和右孩子也加入到队列中。

相比于这道题，我们要解决的问题是，怎么知道当前节点的 level 。

1. 第一种方案

定义一个新的 class，class 里边两个成员 node 和 level，将我们新定义的 class 每次加入到队列中。或者用一个新的队列和之前的节点队列同步入队出队，新的队列存储 level。

下边的代码实现后一种，并且对 level 进行判断。

  1. public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
  2.     List<List<Integer>> ans = new ArrayList<>();
  3.     if (root == null) {
  4.         return ans;
  5.     }
  6.     Queue<TreeNode> treeNode = new LinkedList<>();
  7.     Queue<Integer> nodeLevel = new LinkedList<>();
  8.     treeNode.offer(root);
  9.     int level = 0;
  10.     nodeLevel.offer(level);
  11.     while (!treeNode.isEmpty()) {
  12.         TreeNode curNode = treeNode.poll();
  13.         int curLevel = nodeLevel.poll();
  14.         if (curNode != null) {
  15.             if (ans.size() <= curLevel) {
  16.                 ans.add(new ArrayList<>());
  17.             }
  18.             if ((curLevel % 2) == 0) {
  19.                 ans.get(curLevel).add(curNode.val);
  20.             } else {
  21.                 ans.get(curLevel).add(0, curNode.val);
  22.             }
  23.             level = curLevel + 1;
  24.             treeNode.offer(curNode.left);
  25.             nodeLevel.offer(level);
  26.             treeNode.offer(curNode.right);
  27.             nodeLevel.offer(level);
  28.         }
  29.     }
  30.     return ans;
  31. }

第二种方案

把 102 题 的解释贴过来。

我们在 while 循环中加一个 for 循环，循环次数是循环前的队列中的元素个数即可，使得每次的 while 循环出队的元素都是同一层的元素。

for 循环结束也就意味着当前层结束了，而此时的队列存储的元素就是下一层的所有元素了。

这道题我们要知道当前应该是从左到右还是从右到左，最直接的方案当然是增加一个 level 变量，和上边的解法一样，来判断 level 是奇数还是偶数即可。

  1. public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
  2.     Queue<TreeNode> queue = new LinkedList<TreeNode>();
  3.     List<List<Integer>> ans = new LinkedList<List<Integer>>();
  4.     if (root == null)
  5.         return ans;
  6.     queue.offer(root);
  7.     while (!queue.isEmpty()) {
  8.         int levelNum = queue.size(); // 当前层元素的个数
  9.         List<Integer> subList = new LinkedList<Integer>();
  10.         int level = 0;
  11.         for (int i = 0; i < levelNum; i++) {
  12.             TreeNode curNode = queue.poll();
  13.             if (curNode != null) {
  14.                 if ((level % 2) == 0) {
  15.                     subList.add(curNode.val);
  16.                 } else {
  17.                     subList.add(0, curNode.val);
  18.                 }
  19.                 queue.offer(curNode.left);
  20.                 queue.offer(curNode.right);
  21.             }
  22.         }
  23.         //因为上边 queue.offer(curNode.left) 没有判断是否是 null
  24.         //所以要判断当前是否有元素
  25.         if (subList.size() > 0) {
  26.             ans.add(subList);
  27.         }
  28.         level++;
  29.     }
  30.     return ans;
  31. }

除了增加 level 变量外，我们还可以增加一个 boolean 变量来区别当前从左还是从右。此外 这里 的评论里，看到了另外一种想法，不用添加新的变量。我们直接判断当前 ans 的大小，如果大小是 n 代表当前在添加第 n 层。

解法三

这里 看到一个有趣的想法，分享一下。

我们直接用两个栈（或者队列）轮换着添加元素，一个栈从左到右添加元素，一个栈从右到左添加元素。

  1. public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
  2.     TreeNode c=root;
  3.     List<List<Integer>> ans =new ArrayList<List<Integer>>();
  4.     if(c==null) return ans;
  5.     Stack<TreeNode> s1=new Stack<TreeNode>();
  6.     Stack<TreeNode> s2=new Stack<TreeNode>();
  7.     s1.push(root);
  8.     while(!s1.isEmpty()||!s2.isEmpty())
  9.     {
  10.         List<Integer> tmp=new ArrayList<Integer>();
  11.         while(!s1.isEmpty())
  12.         {
  13.             c=s1.pop();
  14.             tmp.add(c.val);
  15.             if(c.left!=null) s2.push(c.left);
  16.             if(c.right!=null) s2.push(c.right);
  17.         }
  18.         ans.add(tmp);
  19.         tmp=new ArrayList<Integer>();
  20.         while(!s2.isEmpty())
  21.         {
  22.             c=s2.pop();
  23.             tmp.add(c.val);
  24.             if(c.right!=null)s1.push(c.right);
  25.             if(c.left!=null)s1.push(c.left);
  26.         }
  27.         if(!tmp.isEmpty()) ans.add(tmp);
  28.     }
  29.     return ans;
  30. }

总

这道题和 102 题 区别不大，只需要对当前层进行判断即可。解法三用两个栈还是蛮有意思的。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情