思路

题目分析

1. 题目给出我们一棵二叉树
2. 我们要逐层存储结点值到一个数据结构中，并且要按照“之”字的顺序规则存储
3. 也就是说当前一层按照从左到右存储后，下一层要从右到左存储
4. 最终返回这个存储后的结构信息

• 方法一：递归
  • 递归函数意义为前序遍历，并随之记录深度信息
  • 递归函数退出条件是
    • 如果结点为空直接退出
  • 递归函数主体工作任务是
    • 首先根据深度信息查看是否要更新res的空间大小
    • 根据深度信息作为索引，选择是顺序插入res中还是倒序插入到res中
    • 递归左右子树
  • 最终返回res即可
• 方法二：迭代
  • 利用一个队列来存储每一层的结点信息
  • 同样要记录结点深度，判断是否要顺序还是倒序存储，以符合“之”字的规则

方法一：递归

/*
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>> res;                        // 存储最终的结果
    vector<vector<int> > Print(TreeNode* pRoot) {
        PreOrder(pRoot, 0);                         // 递归方法
        return res;
    }
    
    void PreOrder(TreeNode* root, int deep) {
        if(root == NULL) return;                                // 如果为空则直接返回
        if(deep >= res.size()) res.push_back({});               // 按照深度更新res的大小
        if(deep % 2 == 0) res[deep].push_back(root->val);       // 按照深度判断是否应该顺序push_back还是insert到最前面
        else res[deep].insert(res[deep].begin(), root->val);    // 以符合“之”字的要求
        PreOrder(root->left, deep + 1);                         // 前序递归左子节点
        PreOrder(root->right, deep + 1);                        // 前序递归右子节点
    }
    
};

复杂度分析

• 时间复杂度：$O(N)O(N)$，所有的结点都要访问到
• 空间复杂度：$O(logN)O(logN)$，递归栈的空间，与树的深度有关

方法二：迭代

/*
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) {
        if(pRoot == NULL) return {};
        vector<vector<int>> res;
        queue<TreeNode*> q;
        q.push(pRoot);
        int deep = 1;                    // 标记节点深度
        while(!q.empty()) {
            int n = q.size();
            vector<int> level;
            while(n) {
                TreeNode* root = q.front();            // 从队列中循环取出一层的结点
                q.pop();
                level.push_back(root->val);            // 添加到level数据结构中
                if(root->left) q.push(root->left);     // 并将当前结点的下一层子节点压入队列中
                if(root->right) q.push(root->right);
                n--;
            }
            if(deep % 2 == 0) reverse(level.begin(), level.end());    // 如果深度为2的倍数，则应该逆序存储level才符合“之”字的规则
            res.push_back(level);
            deep++;                                                   // 更新深度值
        }
        return res;
    }
    
};

复杂度分析

• 时间复杂度：$O(N)O(N)$，所有的结点都要访问到
• 空间复杂度：$O(logN)O(logN)$，队列的最大空间占用，与树单层结点数量相关