Binary Tree Zigzag Level Order Traversal
Given a binary tree, return thezigzag level ordertraversal 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.
二叉树层序遍历的知识。
使用什么容器可以任君选择。
关键是考查层与层之间的访问顺序是不一样的,需要做一点特殊处理。
总体来说3到4星难度。
class Solution {
public:
vector<vector<int> > zigzagLevelOrder(TreeNode *root)
{
vector<vector<int> > v;
if (!root) return v;
deque<TreeNode *> qt1;
deque<TreeNode *> qt2;
qt1.push_back(root);
vector<int> itmedia;
itmedia.push_back(root->val);
v.push_back(itmedia);
itmedia.clear();
while (!qt1.empty())
{
while (!qt1.empty())
{
TreeNode *t = qt1.back();
qt1.pop_back();
if (t->right)
{
qt2.push_back(t->right);
itmedia.push_back(t->right->val);
}
if (t->left)
{
qt2.push_back(t->left);
itmedia.push_back(t->left->val);
}
}
if (!itmedia.empty()) v.push_back(itmedia);
itmedia.clear();
while (!qt2.empty())
{
TreeNode *t = qt2.back();
qt2.pop_back();
if (t->left)
{
qt1.push_back(t->left);
itmedia.push_back(t->left->val);
}
if (t->right)
{
qt1.push_back(t->right);
itmedia.push_back(t->right->val);
}
}
if (!itmedia.empty()) v.push_back(itmedia);
itmedia.clear();
}
return v;
}
};
//2014-2-16 update
vector<vector<int> > zigzagLevelOrder(TreeNode *root)
{
vector<vector<int> > rs;
if (!root) return rs;
stack<TreeNode *> stk[2];
stk[0].push(root);
bool flag = false;
while (!stk[flag].empty())
{
rs.push_back(vector<int>());
while (!stk[flag].empty())
{
TreeNode * t = stk[flag].top();
stk[flag].pop();
rs.back().push_back(t->val);
if (flag)
{
if (t->right) stk[!flag].push(t->right);
if (t->left) stk[!flag].push(t->left);
}
else
{
if (t->left) stk[!flag].push(t->left);
if (t->right) stk[!flag].push(t->right);
}
}
flag = !flag;
}
return rs;
}
分享到:
相关推荐
我的个人微信公众号:Microstrong 微信公众号ID:MicrostrongAI 微信公众号介绍:Microstrong(小强)同学主要研究机器学习、深度学习、计算机视觉、智能对话系统相关内容,分享在学习过程中的...102. Binary Tree Leve
103 Binary Tree Zigzag Level Order Traversal.js(二叉树之字形级别顺序Traversal.js) 104 Binary Tree.js的最大深度 105从Preorder和Inorder Traversal.js构造二叉树 106从有序和后置Traversal.js构造二叉树 ...
94.Binary_Tree_Inorder_Traversal二叉树的中序遍历【LeetCode单题讲解系列】
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
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility) Java AC版本
105.construct_binary_tree_from_preorder_and_inorder_traversal从前序
144.Binary_Tree_Preorder_Traversal二叉树的前序遍历【LeetCode单题讲解系列】
145.Binary_Tree_Postorder_Traversal二叉树的后序遍历【LeetCode单题讲解系列】
leetcode卡 LeetCode 记录一下再LeetCode上刷的题,坚持每天刷一道吧 2017.06.12 打卡[LeetCode 2. Add Two Numbers], Linked list 2017.06.13 打卡[LeetCode 200. Number of Islands], BFS 2017.06.14 打卡...
102-Binary Tree Level Order Traversal199-Binary Tree Right Side View:层次遍历的一个运用树的构造给出前中后序的序列中的两个,构造一棵树。递归。前序 parent left-child right-child中序 left-child parent ...
Binary Tree Zigzag Level Order Traversal Recover Binary Search Tree Same Tree Symmetric Tree Balanced Binary Tree Flatten Binary Tree to Linked List Populating Next Right Pointers in Each Node II ...
leetcode的题目:Balanced Binary Tree
二叉树前序遍历,leetcode
[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-...
Leetcode-tree 94题 Binary Tree Inorder Traversal 对于树的问题,大多数我们都会使用递归的方法。原因是树的左子树也是树,右子树也是树,使用递归的方法最简单快捷。这道题是需要我们用Inorder的顺序输出节点。in...
BinaryTree.py是一个方便的工具,它可以构建和显示编码时所需的二叉树 演示 您需要在使用之前导入该类 import BinaryTree as bt 从值/对象列表或二叉树构造二叉树 t1 = bt.BinaryTree([1,2,3,4,5,'#',6,7,'#','#','#...
leetcode中文版车鸟 一组用python编写的算法。 种类 冒泡排序 插入排序 归并排序 桶排序 计数排序 基数排序 ...balance_binary_tree ...binary_tree_inorder_traversal ...binary_tree_level_order_traversal_I
* [Binary Search Tree](https://github.com/kamyu104/LeetCode#binary-search-tree) * [Breadth-First Search](https://github.com/kamyu104/LeetCode#breadth-first-search) * [Depth-First Search]...
Source file for LeetCode Permutations Problem