首页 > 代码库 > 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 7return its zigzag level order traversal as:[ [3], [20,9], [15,7]]
难度95，调试老是TLE，看了一下别人的做法，没懂为啥我的超时了。参考这道题其实还是树的层序遍历Binary Tree Level Order Traversal，如果不熟悉的朋友可以先看看哈。不过这里稍微做了一点变体，就是在遍历的时候偶数层自左向右，而奇数层自右向左。在Binary Tree Level Order Traversal中我们是维护了一个队列来完成遍历，而在这里为了使每次都倒序出来，我们很容易想到用栈的结构来完成这个操作。有一个区别是这里我们需要一层一层的来处理（原来可以按队列插入就可以，因为后进来的元素不会先处理），所以会同时维护新旧两个栈，一个来读取，一个存储下一层结点。总体来说还是一次遍历完成，所以时间复杂度是O(n)，空间复杂度最坏是两层的结点，所以数量级还是O(n)（满二叉树最后一层的结点是n/2个）。代码如下：
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 ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {12 ArrayList<ArrayList<Integer>> lists = new ArrayList<ArrayList<Integer>>();13 if (root == null) return lists; 14 LinkedList<TreeNode> stack = new LinkedList<TreeNode>();15 ArrayList<Integer> list = new ArrayList<Integer>();16 stack.push(root);17 list.add(root.val);18 lists.add(list);19 int level = 1;20 while (!stack.isEmpty()) {21 list = new ArrayList<Integer>();22 LinkedList<TreeNode> newstack = new LinkedList<TreeNode>();23 while (!stack.isEmpty()) {24 TreeNode cur = stack.pop();25 if (level % 2 == 0) {26 if (cur.left != null) {27 list.add(cur.left.val);28 newstack.push(cur.left);29 }30 if (cur.right != null) {31 list.add(cur.right.val);32 newstack.push(cur.right);33 }34 }35 else {36 if (cur.right != null) {37 list.add(cur.right.val);38 newstack.push(cur.right);39 }40 if (cur.left != null) {41 list.add(cur.left.val);42 newstack.push(cur.left);43 }44 }45 }46 level++;47 if (list.size()>0) {48 lists.add(list);49 }50 stack = newstack;51 }52 return lists;53 }54 }
贴一下我的做法，不知为何TLE
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 ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {12 ArrayList<ArrayList<Integer>> lists = new ArrayList<ArrayList<Integer>>();13 if (root == null) return lists; 14 LinkedList<TreeNode> stack = new LinkedList<TreeNode>();15 LinkedList<TreeNode> newstack = new LinkedList<TreeNode>();16 stack.add(root);17 int PNuminQ = 1;18 int CNuminQ = 0;19 int level = 0;20 ArrayList<Integer> list = new ArrayList<Integer>();21 while (!stack.isEmpty()) {22 TreeNode cur = stack.pop();23 PNuminQ--;24 list.add(cur.val);25 if (level%2 == 0) {26 if (root.left != null) {27 newstack.push(root.left);28 CNuminQ++;29 }30 if (root.right != null) {31 newstack.push(root.right);32 CNuminQ++;33 }34 }35 else if (level%2 == 1) {36 if (root.right != null) {37 newstack.push(root.right);38 CNuminQ++;39 }40 if (root.left != null) {41 newstack.push(root.left);42 CNuminQ++;43 }44 }45 46 if (PNuminQ == 0) {47 PNuminQ = CNuminQ;48 CNuminQ = 0;49 level++;50 lists.add(list);51 list = new ArrayList<Integer>();52 stack = newstack;53 newstack = new LinkedList<TreeNode>();54 }55 }56 return lists;57 }58 }
Leetcode Binary Tree Zigzag level Order Traversal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。