原题链接:http://oj.leetcode.com/problems/binary-tree-zigzag-level-order-traversal/这道题其实还是树的层序遍历Binary
Tree Level Order Traversal,如果不熟悉的朋友可以先看看哈。不过这里稍微做了一点变体,就是在遍历的时候偶数层自左向右,而奇数层自右向左。在Binary
Tree Level Order Traversal中我们是维护了一个队列来完成遍历,而在这里为了使每次都倒序出来,我们很容易想到用栈的结构来完成这个操作。有一个区别是这里我们需要一层一层的来处理(原来可以按队列插入就可以,因为后进来的元素不会先处理),所以会同时维护新旧两个栈,一个来读取,一个存储下一层结点。总体来说还是一次遍历完成,所以时间复杂度是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有时候考得太多了,面试官会觉得你肯定练过,所以会稍作变体,来考察对于编程和算法的基本理解。
分享到:
相关推荐
Construct Binary Tree from Preorder and Inorder Traversal 根据先序,中序建立二叉树
二叉树的结构特征,以及链式存储结构的特点及程序设计方法
[103_binary-tree-zigzag-level-order-traversal.cpp] [104_maximum-depth-of-binary-tree.cpp] [105_construct-binary-tree-from-preorder-and-inorder-traversal.cpp] [106_construct-binary-tree-from-inorder-...
lru缓存leetcode 1 https://leetcode.com/problems/two-sum/ Two ...https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/ Binary Tree Zigzag Level Order Traversal 104 htt
java lru leetcode what_the_dead_men_say 所以这只是一个 repo,我从leetcode.com存储我的...Zigzag Level Order Traversal - Python3 iterative BFS w Deques 0104 Maximum depth of binary tree - Java Iterative
102.binary-tree-level-order-traversal (二叉树的层序遍历) 104.maximum-depth-of-binary-tree (二叉树的最大深度) 105.construct-binary-tree-from-preorder-and-inorder-traversal (从前序与中序遍历序列构造...
103 Binary Tree Zigzag Level Order Traversal.js(二叉树之字形级别顺序Traversal.js) 104 Binary Tree.js的最大深度 105从Preorder和Inorder Traversal.js构造二叉树 106从有序和后置Traversal.js构造二叉树 ...
102-Binary Tree Level Order Traversal199-Binary Tree Right Side View:层次遍历的一个运用树的构造给出前中后序的序列中的两个,构造一棵树。递归。前序 parent left-child right-child中序 left-child parent ...
94.Binary_Tree_Inorder_Traversal二叉树的中序遍历【LeetCode单题讲解系列】
我的个人微信公众号:Microstrong 微信公众号ID:MicrostrongAI 微信公众号介绍:Microstrong(小强)同学主要研究机器学习、深度学习、计算机视觉、智能对话系统相关内容,分享在学习过程中的...102. Binary Tree Leve
leetcode 树节点leetcode 226 - 反转二叉树 方法一:递归 C# public TreeNode InvertTree ( TreeNode root ) { if ( root == null ) return root ; var temp = root . left ; root . left = root . right ; root . ...
sqlite-netFx40-binary-bundle-Win32-2010-1.0.94.0 解决 “异常来自 HRESULT:0x8007007E” 这个问题。
sqlite-netFx46-binary-bundle-x64-2015-1.0.113.0.zip
binary-tree-postorder-traversal 树 binary-tree-preorder-traversal 链表 linked-list-cycle-ii 链表 linked-list-cycle 链表 copy-list-with-random-pointer 复杂度 single-number 动态规划 candy 贪心 gas-...
leetcode 答案leetcode 的工具 这个项目提供了一些工具来更容易地测试 leetcode 答案。 树:切片 <-> TreeNode 此工具有助于将切片转换为 TreeNode,反之亦然。 Slice2TreeNode: []interface{} -> *model....
sqlite framework 4.0 版本, sqlite-netFx40-binary-x64-2010-1.0.106.0.zip
sqlite-netFx451-static-binary-bundle-x64-2013-1.0.112.0.zip 下错版本了,官网下的好慢,免费分享
sqlite-netFx40-static-binary-x64-2010-1.0.112.0.zip;混合编译,支持32位和64位。
python库,解压后可用。 资源全名:psycopg2_binary-2.8.6-cp38-cp38-win32.whl
psycopg2_binary-2.8.6-cp37-cp37m-manylinux1_x86_64.whl