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

概述

https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/

层次遍历

加个 flag 标记一下当前方向即可。

后悔用 list 了，反正你都得搞出一个临时的 vector 来，不如直接用 vector。

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        vector<vector<int>> ans;
        bool d = false;
        while (!q.empty()) {
            int sz = q.size();
            list<int> t;
            while (sz > 0) {
                auto n = q.front(); q.pop(); sz --;
                if (!n) continue;
                if (d) {
                    t.push_front(n->val);
                } else {
                    t.push_back(n->val);
                }
                q.push(n->left);
                q.push(n->right);
            }
            d = !d;
            if (t.empty()) continue;
            vector<int> tmp(t.begin(), t.end());
            ans.insert(ans.end(), tmp);
        }
        return ans;
    }
};

Links: sword-offer-32-3

未经允许，禁止转载，本文源站链接：https://iamazing.cn/