102. Binary Tree Level Order Traversal

bfs O(n) time O(n) space

/**
 * 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>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode *> q;
        q.push(root);
        while (!q.empty()) {
            res.push_back({});
            for (int i = size(q); i > 0; --i) {
                auto p = q.front(); q.pop();
                if (!p) continue;
                res.back().push_back(p->val);
                q.push(p->left);
                q.push(p->right);
            }
        }
        if (res.back().empty()) { // 别忘了最后要弹出空数组
            res.pop_back();
        }
        return res;
    }
};

/**
 * 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>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if (!root) return res;
        queue<pair<TreeNode *, int>> q;
        q.emplace(root, 0);
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            if (p.first) {
                if (p.second < res.size()) res[p.second].push_back(p.first->val);
                else res.push_back({p.first->val});
                q.emplace(p.first->left, p.second + 1);
                q.emplace(p.first->right, p.second + 1);
            }
        }
        return res;
    }
};

preorder traversal O(n) time O(1) extra space

/**
 * 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>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        preorder(root, res, 0);
        return res;
    }

    void preorder(TreeNode *root, vector<vector<int>> &res, int lvl) {
        if (!root) return;
        if (res.size() == lvl) {
            res.resize(lvl + 1);
        }
        res[lvl].push_back(root->val);
        preorder(root->left, res, lvl + 1);
        preorder(root->right, res, lvl + 1);
    }
};