原题链接: http://oj.leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
这道题事实上还是树的层序遍历Binary Tree Level Order Traversal,假设不熟悉的朋友能够先看看哈。
这道题事实上还是树的层序遍历Binary Tree Level Order Traversal,假设不熟悉的朋友能够先看看哈。
只是这里略微做了一点变体,就是在遍历的时候偶数层自左向右,而奇数层自右向左。
在
Binary Tree Level Order Traversal中我们是维护了一个队列来完毕遍历,而在这里为了使每次都倒序出来,我们非常easy想到用栈的结构来完毕这个操作。有一个差别是这里我们须要一层一层的来处理(原来能够按队列插入就能够。由于后进来的元素不会先处理),所以会同一时候维护新旧两个栈,一个来读取,一个存储下一层结点。整体来说还是一次遍历完毕。所以时间复杂度是O(n),空间复杂度最坏是两层的结点,所以数量级还是O(n)(满二叉树最后一层的结点是n/2个)。代码例如以下:public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) { ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); if(root==null) return res; LinkedList<TreeNode> stack = new LinkedList<TreeNode>(); int level=1; ArrayList<Integer> item = new ArrayList<Integer>(); item.add(root.val); res.add(item); stack.push(root); while(!stack.isEmpty()) { LinkedList<TreeNode> newStack = new LinkedList<TreeNode>(); item = new ArrayList<Integer>(); while(!stack.isEmpty()) { TreeNode node = stack.pop(); if(level%2==0) { if(node.left!=null) { newStack.push(node.left); item.add(node.left.val); } if(node.right!=null) { newStack.push(node.right); item.add(node.right.val); } } else { if(node.right!=null) { newStack.push(node.right); item.add(node.right.val); } if(node.left!=null) { newStack.push(node.left); item.add(node.left.val); } } } level++; if(item.size()>0) res.add(item); stack = newStack; } return res; }上面的算法事实上还是一次广度优先搜索,仅仅是在读取每一层结点交替的交换顺序。
毕竟面试中像
Binary Tree Level Order Traversal有时候考得太多了。面试官会认为你肯定练过。所以会稍作变体,来考察对于编程和算法的基本理解。