首页 > 代码库 > [leetcode] Binary Tree Zigzag Level Order Traversal
[leetcode] Binary Tree Zigzag Level Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes‘ values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree {3,9,20,#,#,15,7},
3 / 9 20 / 15 7
return its zigzag level order traversal as:
[ [3], [20,9], [15,7]]
https://oj.leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
思路：跟层序遍历类似，用queue来做，用null分隔每一层，然后
public class Solution { public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<List<Integer>>(); if (root == null) return res; Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.add(root); queue.add(null); boolean odd = true; List<Integer> tmp = new ArrayList<Integer>(); while (!queue.isEmpty()) { TreeNode node = queue.remove(); if (node == null) { if (odd) res.add(new ArrayList<Integer>(tmp)); else { Collections.reverse(tmp); res.add(new ArrayList<Integer>(tmp)); } tmp.clear(); odd = !odd; if (!queue.isEmpty()) queue.add(null); } else { // System.out.println(node.val); tmp.add(node.val); if (node.left != null) queue.add(node.left); if (node.right != null) queue.add(node.right); } } return res; } public static void main(String[] args) { TreeNode root = new TreeNode(3); root.left = new TreeNode(9); root.right = new TreeNode(20); root.right.left = new TreeNode(15); root.right.right = new TreeNode(7); System.out.println(new Solution().zigzagLevelOrder(root)); }}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。