首页 > 代码库 > 39.2: Binary Tree Zigzag Level Order Traversal
39.2: Binary Tree Zigzag Level Order Traversal
/************************************************************************/
/* 38: 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]
]
* */
/*** 树的按照层遍历 ，类似 BFS***********************************************************/
public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); List<TreeNode> level = new ArrayList<>(); level.add(root); boolean leftflag=true; while(true){ if (level.isEmpty() || level.get(0) == null){ break; } List<TreeNode> nextLevel = new ArrayList<>(); List<Integer> currentLevel = new ArrayList<>(); if(leftflag) //left to right { for (TreeNode node : level){ currentLevel.add(node.val); if (node.left != null) nextLevel.add(node.left); if (node.right != null) nextLevel.add(node.right); } } else { for(int i=level.size()-1;i>=0;i--) { currentLevel.add(level.get(i).val); if (level.get(level.size()-1-i).left != null) nextLevel.add(level.get(level.size()-1-i).left); if (level.get(level.size()-1-i).right != null) nextLevel.add(level.get(level.size()-1-i).right); } } result.add(currentLevel); level = nextLevel; leftflag=!leftflag; } return result; }
39.2: Binary Tree Zigzag Level Order Traversal