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

孜孜不倦fly / 2023-08-07 / 原文

题目：

解法一：

class Solution {
public:
    void traversal(TreeNode* cur, vector<vector<int>>& result, int depth){
        if(cur==nullptr) return;
        if(result.size()==depth) result.push_back(vector<int>());
        result[depth].push_back(cur->val);
        traversal(cur->left, result, depth+1);
        traversal(cur->right, result, depth+1);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        int depth=0;
        traversal(root, result, depth);
        for(int i=0;i<result.size();i++){                                 //取巧的方法，即将按照正常层序遍历得到的结果按层进行重排序
            if(i%2==1) reverse(result[i].begin(), result[i].end());
        }
        return result;
    }
};

解法二：
class Solution {
public:
vector<vector> zigzagLevelOrder(TreeNode* root) {
vector<vector> result;
if (!root) {
return result;
}

    queue<TreeNode*> nodeQueue;
    nodeQueue.push(root);
    bool isOrderLeft = true;                //判断插入顺序的标志位，true为从左到右，false为从右到左

    while (!nodeQueue.empty()) {
        deque<int> levelList;               //使用队列法的关键就在于，存储每一层元素用的是队列而不是向量，这样就可以按层调整插入的顺序
        int size = nodeQueue.size();
        for (int i = 0; i < size; ++i) {
            auto node = nodeQueue.front();  //读取节点的顺序依然是从左到右
            nodeQueue.pop();
            if (isOrderLeft) {
                levelList.push_back(node->val);
            } else {
                levelList.push_front(node->val);
            }
            if (node->left) {
                nodeQueue.push(node->left);
            }
            if (node->right) {
                nodeQueue.push(node->right);
            }
        }
        result.push_back(vector<int>{levelList.begin(), levelList.end()});
        isOrderLeft = !isOrderLeft;
    }

    return ans;
}

};
解法二来自力扣官方题解