首页 > 代码库 > 【leetcode】Binary Tree Zigzag Level Order Traversal (middle)
【leetcode】Binary Tree Zigzag Level Order Traversal (middle)
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 7
return its zigzag level order traversal as:
[ [3], [20,9], [15,7]]
思路:由于需要排成之字形,所以用一个栈来存储当前行的内容,另一个栈来存储下一行的内容。
以根为第0层,那么偶数层都应该从左向右输出。那么每次遇到偶数层,压入下一层奇数层时就按从左到右的顺序,这样弹栈时就是从右到左。
纠结了一会儿,AC了。
class Solution {public: vector<vector<int> > zigzagLevelOrder(TreeNode *root) { vector<vector<int>> ans; if(root == NULL) { return ans; } int level = 0; //记录当前层号 vector<TreeNode *> curlevel; curlevel.push_back(root); while(!curlevel.empty()) { vector<int> partans; vector<TreeNode *> nextlevel; if(level % 2 == 0) //偶数层,根是第0层 { while(!curlevel.empty()) //本层不为空 { if(curlevel.back()->left != NULL) //先压入左边,再压入右边 { nextlevel.push_back(curlevel.back()->left); } if(curlevel.back()->right != NULL) { nextlevel.push_back(curlevel.back()->right); } partans.push_back(curlevel.back()->val); curlevel.pop_back(); } ans.push_back(partans); curlevel = nextlevel; } else { while(!curlevel.empty()) //本层不为空 { if(curlevel.back()->right != NULL) //先压入右边,再压入左边 { nextlevel.push_back(curlevel.back()->right); } if(curlevel.back()->left != NULL) { nextlevel.push_back(curlevel.back()->left); } partans.push_back(curlevel.back()->val); curlevel.pop_back(); } ans.push_back(partans); curlevel = nextlevel; } level++; } return ans; } void createTree(TreeNode * &root) { int n; cin >> n; if(n != 0) { root = new TreeNode(n); createTree(root->left); createTree(root->right); } }};
看看别人的答案。思路不一样。
class Solution {vector<vector<int> > result;public:vector<vector<int> > zigzagLevelOrder(TreeNode *root) { if(root!=NULL) { traverse(root, 0); } for(int i=1;i<result.size();i+=2) { vector<int>* v = &result[i]; std:reverse(v->begin(), v->end()); } return result;}void traverse(TreeNode* node, int level){ if(node == NULL) return; vector<int>* row = getRow(level); row->push_back(node->val); traverse(node->left, level+1); traverse(node->right, level+1);}vector<int>* getRow(int level){ if(result.size()<=level) { vector<int> newRow; result.push_back(newRow); } return &result[level];}};
【leetcode】Binary Tree Zigzag Level Order Traversal (middle)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。