[LeetCode]103. Binary Tree Zigzag Level Order Traversal

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

返回Z型遍历的树

我的解法：

非递归

public class Solution { public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> res = new LinkedList(); if (root == null) { return res; } Queue<TreeNode> queue = new LinkedList(); queue.offer(root); boolean flag = true; while (!queue.isEmpty()) { int size = queue.size(); List<Integer> list = new LinkedList(); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } if (flag) { list.add(node.val); } else { list.add(0, node.val); } } res.add(new LinkedList(list)); flag = !flag; } return res; } }

二叉树的前序遍历的话，同一层里面的节点一定是左边节点先遍历，右边节点后遍历。

递归法： 传一个参数，当前遍历的层数，前序遍历

public class Solution { public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> res = new LinkedList(); travel(root, res, 0); return res; } private void travel(TreeNode root, List<List<Integer>> res, int level) { if (root == null) { return; } if (res.size() <= level) { res.add(new LinkedList()); } List<Integer> list = res.get(level); if (level % 2 == 0) { list.add(root.val); } else { list.add(0, root.val); } travel(root.left, res, level + 1); travel(root.right, res, level + 1); } }