《剑指offer刷题笔记》33、之字形打印二叉树【c++详细题解】

逃离我推掉我的手 2021-07-24 14:55 294阅读 0赞

### **题目** ###

请实现一个函数按照之字形顺序从上向下打印二叉树。

即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

**样例**

输入如下图所示二叉树[8, 12, 2, null, null, 6, 4, null, null, null, null]
        8
       / \
      12  2
         / \
        6   4
    输出：[[8], [2, 12], [6, 4]]

### **思路** ###

在上一题的基础上加一个标记，奇数行为从左到右，偶数行为从右到左。

### **代码** ###

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
    class Solution { 
    public:
        vector<vector<int>> printFromTopToBottom(TreeNode* root) { 
            vector<vector<int>>res;
            if(!root) return res;
            queue<TreeNode*>q;
            vector<int>level; //记录一层的节点
            q.push(root);
            q.push(NULL);// 一层的结尾标记
            bool flag = false;
            while(q.size())
            { 
                auto t = q.front();
                q.pop();
                if(!t)
                { 
                    if(!level.size()) break;
                    if(flag) reverse(level.begin(),level.end());
                    res.push_back(level);
                    level.clear();
                    q.push(NULL);
                    flag = !flag;
                }
                else
                { 
                    level.push_back(t->val);
                    if(t->left) q.push(t->left);
                    if(t->right) q.push(t->right);
                }
            }
            return res;
        }
    };