首页 > 代码库 > leetcode Binary Tree Zigzag Level Order Traversal
leetcode Binary Tree Zigzag Level Order Traversal
给定一个树，按照Z字形记录每一行。例如：
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]]
这题想了有一会，按照上一题思路的启发。这题也是应该要用某个数据结构会比较好解答。然后就想用队列，然后可以任意从前面删除就好了，可以队列之提供后面pop的操作。于是就想到用栈。
思路：用两个栈，每个栈存一层，例如上一题，第一个栈sta1，先push(3)，然后去sta1的元素左边右边先后入sta2，那么再pop就是20,9了，当然pop的时候又要对其进行push栈sta1，先把7push然后15push，最后栈sta1 pop的时候就是15,7了。
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:vector<vector<int> > zigzagLevelOrder(TreeNode *root){ vector<vector<int> > ans; if (!root) return ans; vector<int> tmp; stack<TreeNode *> sta1, sta2; TreeNode *p; sta1.push(root); while(!sta1.empty() || !sta2.empty()) { while (!sta1.empty()) { p = sta1.top(); sta1.pop(); tmp.push_back(p -> val); if (p -> left) sta2.push(p -> left); if (p -> right) sta2.push(p -> right); } ans.push_back(tmp); tmp.clear(); if (sta1.empty() && sta2.empty()) return ans; while(!sta2.empty()) { p = sta2.top(); sta2.pop(); tmp.push_back(p -> val); if (p -> right) sta1.push(p -> right); if (p -> left) sta1.push(p -> left); } ans.push_back(tmp); tmp.clear(); } return ans;}};
leetcode Binary Tree Zigzag Level Order Traversal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。