首页 > 代码库 > leetcode 刷题之路 63 Binary Tree Zigzag Level Order Traversal
leetcode 刷题之路 63 Binary Tree Zigzag Level Order Traversal
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] ]
题目要求,按照zigzag的顺序访问树。这道题算是树的层序遍历的一个变种。
回想之前写树的层序遍历时,利用队列来辅助操作,访问当前节点的同时,将树的左右孩子push到队列当中,这样当上一次节点访问完成后,下一层节点已经全部按照顺序加入到了队列当中。若要以zigzag的形式访问,当上一层访问完成后,下一层的节点要逆序访问。要达到这个目的,我们自然而然会想到先进后出的栈,访问上一层节点时将其左右孩子入栈,然后再按照出栈的顺序访问下一层节点,得到的顺序正好和上一次节点访问顺序相反。当然,一个栈是不够用的,否则孩子节点压入栈后,覆盖了尚未访问的上一层节点,就成了树的先序遍历了。
程序中使用两个栈s1,s2来辅助操作,s1中储存奇数层(从1开始计算)的节点,奇数层的遍历顺序是从左到右,所以节点应该以从右向左的顺序压入栈s1中,s2中储存偶数层(从1开始计算)的节点,偶数层的遍历顺序是从右向左,所以节点应该以从左到右的顺序压入栈s2中,体现在程序上,就是节点右孩子先于左孩子压入栈s1中,节点左孩子先于右孩子压入栈s2中,只要初始顺序正确,下面s1,s2来回倒腾,顺序是定死的。
AC code:
/** * 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<int> temp; vector<vector<int>> ret; if(root==NULL) return ret; stack<TreeNode*> s1,s2; s1.push(root); while(!s1.empty()||!s2.empty()) { if(!s1.empty()) { temp.clear(); while(!s1.empty()) { root=s1.top(); temp.push_back(root->val); if(root->left!=NULL) s2.push(root->left); if(root->right!=NULL) s2.push(root->right); s1.pop(); } ret.push_back(temp); } if(!s2.empty()) { temp.clear(); while(!s2.empty()) { root=s2.top(); temp.push_back(root->val); if(root->right!=NULL) s1.push(root->right); if(root->left!=NULL) s1.push(root->left); s2.pop(); } ret.push_back(temp); } } } };