首页 > 代码库 > Lintcode 71 Binary Tree Zigzag Level Order Traversal
Lintcode 71 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).
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] ]
Java Version 用count计数实现奇数层reverse
1 /** 2 3 Definition of TreeNode: 4 public class TreeNode { 5 public int val; 6 public TreeNode left, right; 7 public TreeNode(int val) { 8 this.val = val; 9 this.left = this.right = null; 10 } 11 }*/ 12 public class Solution { 13 14 /** 15 * @param root: The root of binary tree. 16 * @return: A list of lists of integer include 17 * the zigzag level order traversal of its nodes‘ values 18 */ 19 public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) { 20 // write your code here 21 ArrayList <ArrayList<Integer>> result = new ArrayList(); 22 23 if (root == null) { 24 return result; 25 } 26 Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(root); 27 int count = 0; 28 while(!queue.isEmpty()){ 29 30 int size = queue.size(); 31 ArrayList<Integer> level = new ArrayList<Integer>(); 32 33 for(int i=0; i<size; i++){ 34 35 TreeNode head = queue.poll(); 36 level.add(head.val); 37 if(head.left!=null) queue.offer(head.left); 38 if(head.right!=null) queue.offer(head.right); 39 } 40 if(count%2 == 1) Collections.reverse(level); 41 count++; 42 result.add(level); 43 } 44 return result; 45 } 46 }
C++Version
我们用到栈的后进先出的特点,这道题我们维护两个栈,相邻两行分别存到两个栈中,进栈的顺序也不相同,一个栈是先进左子结点然后右子节点,另一个栈是先进右子节点然后左子结点,这样出栈的顺序就是我们想要的之字形了
1 /** 2 3 Definition of TreeNode: 4 class TreeNode { 5 public: 6 int val; 7 TreeNode left, right; 8 TreeNode(int val) { 9 this->val = val; 10 this->left = this->right = NULL; 11 } 12 }*/ 13 class Solution { 14 15 /** 16 * @param root: The root of binary tree. 17 * @return: A list of lists of integer include 18 * the zigzag level order traversal of its nodes‘ values 19 */ 20 public: 21 22 vector<vector<int>> zigzagLevelOrder(TreeNode *root) { 23 // write your code here 24 vector<vector<int>> res; 25 if(!root) return res; 26 27 stack<TreeNode*> s1; 28 stack<TreeNode*> s2; 29 30 s1.push(root); 31 vector<int> level; 32 33 while(!s1.empty() || !s2.empty()){ 34 while(!s1.empty()){ 35 TreeNode *cur = s1.top(); 36 s1.pop(); 37 level.push_back(cur->val); 38 if(cur->left) s2.push(cur->left); 39 if(cur->right) s2.push(cur->right); 40 } 41 if(!level.empty()) 42 res.push_back(level); 43 level.clear(); 44 while(!s2.empty()){ 45 TreeNode *cur = s2.top(); 46 s2.pop(); 47 level.push_back(cur->val); 48 if(cur->right) s1.push(cur->right); 49 if(cur->left) s1.push(cur->left); 50 } 51 if(!level.empty()) 52 res.push_back(level); 53 level.clear(); 54 } 55 return res; 56 } 57 };
Lintcode 71 Binary Tree Zigzag Level Order Traversal
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。