314. Binary Tree Vertical Order Traversal - cocoder39/coco39_LC GitHub Wiki

314. Binary Tree Vertical Order Traversal

Notes 2020:

class Solution:
    def verticalOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        queue = collections.deque([(root, 0)])
        index_to_vals = collections.defaultdict(list)
        
        min_left = max_right = 0
        while queue:
            sz = len(queue)
            for i in range(sz):
                cur, index = queue.popleft()
                index_to_vals[index].append(cur.val)
                min_left = min(min_left, index)
                max_right = max(max_right, index)
                if cur.left:
                    queue.append((cur.left, index-1))
                if cur.right:
                    queue.append((cur.right, index+1))
        
        res = []
        for index in range(min_left, max_right + 1):
            if index in index_to_vals:
                res.append(index_to_vals[index])
        return res

=============================================================================

tips:

  • bfs with the help of queue nodeQ
  • another queue idxQ records the corresponding column of node in nodeQ, it follows nodeQ all the way
  • unordered_map maps value in the same col to same vector (cons: worst case is O(n); memory overhead)

time is O(n) and space is O(n)

vector<vector<int>> verticalOrder(TreeNode* root) {
        vector<vector<int>> verticalOrder(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> nodeQ;
        queue<int> idxQ; //keep track of the idx of node in nodeQ
        if (root) {
            nodeQ.push(root);
            idxQ.push(0);
        } else {
            return res;
        }
        
        unordered_map<int, vector<int>> mp; 
        int left = INT_MAX, right = INT_MIN; //use unordered_map instead of map if keeping track of boundaries 
        while (! nodeQ.empty()) {
            TreeNode* node = nodeQ.front();
            int idx = idxQ.front();
            nodeQ.pop();
            idxQ.pop();
            
            mp[idx].push_back(node->val);
            left = min(left, idx);
            right = max(right, idx);
            
            if (node->left) {
                nodeQ.push(node->left);
                idxQ.push(idx - 1);
            } 
            if (node->right) {
                nodeQ.push(node->right);
                idxQ.push(idx + 1);
            }
        }
        
        for (int i = left; i <= right; i++) {
            res.push_back(mp[i]);
        }
        return res;
    }

deque: O(1) for [], push_front(), push_back(). Deque can be replaced by two vector (reverse the left vector at the end)

vector<vector<int>> verticalOrder(TreeNode* root) {
        vector<vector<int>> res;
        if (! root) {
            return res;
        }
        
        deque<vector<int>> dq;
        queue<TreeNode*> nodeQ;
        queue<int> idxQ;
        nodeQ.push(root);
        idxQ.push(0);
        int start = 0;
        while (! nodeQ.empty()) {
            TreeNode* node = nodeQ.front();
            int idx = idxQ.front();
            nodeQ.pop();
            idxQ.pop();
            
            if (idx - start + 1 > dq.size()) {
                dq.push_back({node->val});
            } else if (idx < start) {
                dq.push_front({node->val});
            } else {
                dq[idx - start].push_back(node->val);
            }
            start = min(start, idx);
            
            if (node->left) {
                nodeQ.push(node->left);
                idxQ.push(idx - 1);
            } 
            if (node->right) {
                nodeQ.push(node->right);
                idxQ.push(idx + 1);
            }
        }
        
        while (! dq.empty()) {
            res.push_back(dq.front());
            dq.pop_front();
        }
        return res;
    }

doubly linked list

vector<vector<int>> verticalOrder(TreeNode* root) {
        vector<vector<int>> res;
        if (! root) return res;
        
        queue<TreeNode*> nodeQ;
        nodeQ.push(root);
        
        list<vector<int>> mylist;
        mylist.push_back(vector<int>());
        (*mylist.begin()).push_back(root->val);
        
        queue<list<vector<int>>::iterator> itQ;
        itQ.push(mylist.begin());
        
        while (! nodeQ.empty()) {
            TreeNode* node = nodeQ.front();
            auto it = itQ.front();
            nodeQ.pop();
            itQ.pop();
            
            if (node->left) {
                if (it == mylist.begin()) {
                    mylist.push_front(vector<int>());
                }
                (*prev(it)).push_back(node->left->val);
                
                nodeQ.push(node->left);
                itQ.push(prev(it));
            }
            if (node->right) {
                if (next(it) == mylist.end()) {
                    mylist.push_back(vector<int>());
                }
                (*next(it)).push_back(node->right->val);
                
                nodeQ.push(node->right);
                itQ.push(next(it));
            }
        }
        
        for (auto it = mylist.begin(); it != mylist.end(); it++) {
            res.push_back(*it);
        }
        return res;
    }
⚠️ **GitHub.com Fallback** ⚠️