C++ Layer travesal without using queue


  • 0
    W

    In standard layer traversal technique, we cannot differentiate whether the element in queue has moved to the next layer.
    To address this issue we use two vectors instead, one for node in current layer, and put there children (nodes of next layer) in the other vector. They are swapped after a layer has been traversed.

    class Solution {
    public:
        vector<int> largestValues(TreeNode* root) {
            vector<int> result;
            if (root==NULL) return result;
            vector<TreeNode*> cur;
            vector<TreeNode*> next;
            cur.push_back(root);
            while (!cur.empty()) {
                int m = INT_MIN;
                for (auto p : cur) {
                    m = max(m, p->val);
                    if (p->left) next.push_back(p->left);
                    if (p->right) next.push_back(p->right);                
                }
                result.push_back(m);
                swap(cur, next);
                next.clear();
            }
            return result;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.