首页 > 代码库 > 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]]
confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.
Solution:
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */10 public class Solution {11 public List<List<Integer>> zigzagLevelOrder(TreeNode root) {12 List<List<Integer>> res = new ArrayList<List<Integer>>();13 if (root==null) return res;14 15 List<List<TreeNode>> nodeSet = new ArrayList<List<TreeNode>>();16 List<TreeNode> oneLevel = new ArrayList<TreeNode>();17 nodeSet.add(oneLevel);18 oneLevel.add(root);19 boolean left = false;20 int index = 0;21 while (index<nodeSet.size()){22 List<TreeNode> curLevel = nodeSet.get(index);23 oneLevel = new ArrayList<TreeNode>();24 for (int i=curLevel.size()-1;i>=0;i--){25 TreeNode curNode = curLevel.get(i);26 if (left){27 if (curNode.left!=null) oneLevel.add(curNode.left);28 if (curNode.right!=null)oneLevel.add(curNode.right);29 } else {30 if (curNode.right!=null) oneLevel.add(curNode.right);31 if (curNode.left!=null) oneLevel.add(curNode.left);32 }33 }34 if (oneLevel.size()>0) nodeSet.add(oneLevel);35 left = !left;36 index++;37 }38 39 for (int i=0;i<nodeSet.size();i++){40 oneLevel = nodeSet.get(i);41 List<Integer> oneRes = new ArrayList<Integer>();42 for (int j=0;j<oneLevel.size();j++)43 oneRes.add(oneLevel.get(j).val);44 res.add(oneRes);45 }46 47 return res; 48 }49 }
Leetcode-binary Tree Zigzag Level Order Traversal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。