按之字型打印二叉树
include
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {</int>
vector<int> resRow; vector<vector<int> >res; if(!pRoot) return res; stack<TreeNode*> sta[2]; //两个栈 int current = 1; int next = 0; sta[current].push(pRoot); //先往当前栈内存入根节点 while(!sta[current].empty()) //当当前栈非空时进行循环 { if(current) //当当前栈的下标为奇数时,先向下一层的栈内存放左孩子 { if(sta[current].top()->left) sta[next].push(sta[current].top()->left); if(sta[current].top()->right) sta[next].push(sta[current].top()->right); } else{ //若为偶数,每个结点先存放右孩子 if(sta[current].top()->right) sta[next].push(sta[current].top()->right); if(sta[current].top()->left) sta[next].push(sta[current].top()->left); } //在当前栈出栈 resRow.push_back(sta[current].top()->val); sta[current].pop(); //当前元素出栈 if(sta[current].empty()) //当当前栈为空时 { current = 1-current; //调换两个栈,next变成当前栈了 next = 1-next; res.push_back(resRow); //当当前栈全部存入resRow之后再整体存入到二维结果数组中 resRow.clear(); } } return res; }
};