题解 | #按之字形顺序打印二叉树#

按之字形顺序打印二叉树

https://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0

//主要思路是设计一个标记nowToleft:
//记录当前是从左往右打印(nowToLeft=true)还是从右往左打印(nowToleft=false).
//然后准备一个栈,如果当前从左往右,则先压左再压右;否则,先压右再压左。往复这个过程就可以完成了。
#include <vector>
class Solution {
  public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        // write code here
        stack<TreeNode*> layerStack;
        stack<TreeNode*> restoreStack;
        stack<TreeNode*> empty;
        vector<vector<int>> result;
        vector<int> tempVec;

        if(pRoot == nullptr){
            return result;
        }

        bool nowToLeft = true;
        layerStack.push(pRoot);
        restoreStack.push(pRoot);
        while (!restoreStack.empty()) {
            restoreStack = empty;
            while (!layerStack.empty()) {
                pRoot = layerStack.top();
                tempVec.push_back(pRoot->val);
                layerStack.pop();

                if (nowToLeft) {
                    if(pRoot->left != nullptr)
                        restoreStack.push(pRoot->left);
                    if(pRoot->right != nullptr)
                        restoreStack.push(pRoot->right);
                } else {
                    if(pRoot->right != nullptr)
                        restoreStack.push(pRoot->right);
                    if(pRoot->left != nullptr)
                        restoreStack.push(pRoot->left);
                }
            }
            nowToLeft = !nowToLeft;
            layerStack = restoreStack;
            result.push_back(tempVec);
            tempVec.clear();
        }
        return result;
    }
};

全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 17:16
科大讯飞 算法工程师 28.0k*14.0, 百分之三十是绩效,惯例只发0.9
点赞 评论 收藏
分享
废铁汽车人:秋招真是牛鬼蛇神齐聚一堂
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务