题目描述
请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。
思路:
1.第一种按照层序遍历,然后偶数行(默认从第一行开始)翻转即可,层序遍历和翻转可参考
https://blog.csdn.net/weixin_42513339/article/details/89054156
https://blog.csdn.net/weixin_42513339/article/details/89251861
但是该方法遇到海量数据效率太低,所以这里我们可以用两个栈来实现,避免了翻转
2.栈实现,就是不断压入,弹出时第二个栈压入该元素的左右(或者右左),这里设奇数行从左往右压入,偶数行从左往右
假设如下
那么先压入8,弹出时,由于第一行,所以从左往右压入,即第二个栈压入6,10;
由于栈是先进后出,所以弹出时,先弹出10,由于是偶数行从右往左,然后第二个栈压入11,9;同理在6 时压入7,5;
最后弹出的便是 5 ,7 ,9 ,11;
代码如下:
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int>>ans;
if(pRoot == NULL)
return ans;
stack<TreeNode*>ms;
stack<TreeNode*>ms2;
int high = 1;
ms.push(pRoot);
while(!ms.empty())
{
vector<int>m;
while(!ms.empty())
{
m.push_back((ms.top())->val);
if(high % 2 == 1)
{
if(ms.top()->left != NULL)
ms2.push(ms.top()->left);
if(ms.top()->right != NULL)
ms2.push(ms.top()->right);
}
else
{
if(ms.top()->right != NULL)
ms2.push(ms.top()->right);
if(ms.top()->left != NULL)
ms2.push(ms.top()->left);
}
ms.pop();
}
ans.push_back(m);
high++;
ms.swap(ms2);
}
return ans;
}
};