剑指 Offer 32 - III. 从上到下打印二叉树 III

请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。

例如:
  给定二叉树: [3,9,20,null,null,15,7],

        3
          /  \
                          9   20
                               /  \
                            15   7
返回其层次遍历结果:[[3],[20,9],[15,7]]

=====================================================

相比32-II加了一个判断,判断是插在数组的前面还是后面

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> v;
        if (root == NULL)
            return v;
        queue<TreeNode *> q;
        q.push(root);
        int i = 0;
        while (!q.empty()) {
            q.push(NULL);
            TreeNode* r = q.front();
            vector<int> t;
            while (r != NULL) {
                if (i % 2 == 0)
                    t.push_back(r->val);
                else
                    t.insert(t.begin(), r->val);
                if (r->left)
                    q.push(r->left);
                if (r->right)
                    q.push(r->right);
                q.pop();
                r = q.front();
            }
            q.pop();
            if (t.size() != 0) {
                v.push_back(t);
                i++;
            }
        }
        return v;
    }
};

看题解,这个题目貌似是想考察双端队列,但是没有什么必要性,其实是双端队列自己不怎么熟悉,又熟悉了一下,c++的deque不太好做,看到一个大神写的用双栈实现的类似双端丢列的写法,跪了

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(root==NULL)      return {};
        stack<TreeNode*> s1; //管理第0层等偶数层
        stack<TreeNode*> s2; // 管理第1层等奇数层
        vector<vector<int>> res;
        s1.push(root);
        int count = 0;
        while(!s1.empty() || !s2.empty()){
            vector<int> temp;
            if(count%2==0){
                int len = s1.size();
                for(int i=0;i<len;i++){
                    temp.push_back(s1.top()->val);
                    if(s1.top()->left)    s2.push(s1.top()->left);
                    if(s1.top()->right)     s2.push(s1.top()->right);
                    s1.pop();
                }
            }
            else{
                int len = s2.size();
                for(int i=0;i<len;i++){
                    temp.push_back(s2.top()->val);
                    if(s2.top()->right)    s1.push(s2.top()->right);
                    if(s2.top()->left)     s1.push(s2.top()->left);
                    s2.pop();
                }
            }
            count++;
            res.push_back(temp);
        }
        return res;
    }
};

 

上一篇:使用adb连接夜神模拟器报错adb server version (36) doesn't match this client (41); killing...


下一篇:You can't access this shared folder because your organization's security policies block unauthenticated guest access. These policies help protect your PC