【2024考研】题解19 | #按之字形顺序打印二叉树#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <algorithm>
#include <queue>
#include <vector>
class Solution {
public:
    /**
     * @param pRoot TreeNode类 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > Print(TreeNode* pRoot) {
        // write code here
        vector<vector<int>> ans;
        //特例为空
        if(pRoot == NULL) return ans;

        TreeNode *head = pRoot;
        queue<TreeNode*> q;
        q.push(head);

        TreeNode *now;
        bool flag = true;//第一次循环为奇数

        while (!q.empty()) {
            vector<int> row;
            int n = q.size();

            flag = !flag;//每循环一次 奇变偶 偶变奇

            for(int i = 0; i < n; i++){
                now = q.front();
                q.pop();
                row.push_back(now->val);

                if(now->left) q.push(now->left);
                if(now->right) q.push(now->right);
            }
            //奇数行翻转，偶数行不变
            if(flag) reverse(row.begin(), row.end());

            ans.push_back(row);
        
        }
        return ans;
        //总体是在层序遍历上利用flag区别开——奇数行|偶数行
    }
};

算法思想：

-1 使用队列进行层序遍历，同时使用一个flag来标记当前层是奇数行还是偶数行。

-2 在每一层的遍历过程中，将节点的值存入当前行的vector中，并将其左右子节点加入队列。

-3 如果当前层是奇数行，则将当前行的vector翻转。

-4 将每一行的vector加入结果数组中。

-4 最后返回结果数组。

时间复杂度：

O(n)，其中n是二叉树的节点个数。需要遍历每个节点一次。

空间复杂度：

O(k)，其中k是最大的一层节点个数。需要使用一个队列来存储层序遍历的节点，以及一个二维数组来存储结果。