C++ solution using DFS


  • 0
    A
    /**
     * 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>> verticalOrder(TreeNode* root) {
            unordered_map<int, vector<int>> values;
            vector<vector<int>> results;
            int min = 0;
            int max = 0;
            
            if (root != NULL) {
                traverseTree(root, min, max, values);
                for(int i = min; i <= max; ++i) {
                    results.push_back(values[i]);
                }
            }
            
            return results;
        }
        
    protected:
        void traverseTree(TreeNode *root, int &min, int &max, unordered_map<int, vector<int>> &values) {
            struct NodeValue {
                NodeValue(TreeNode *n, int val) : node(n), value(val)
                {}
                
                TreeNode *node;
                int value;
            };
            
            int current = 0;
            queue<NodeValue> q;
            
            q.push(NodeValue(root, current));
            while(!q.empty()) {
                NodeValue val = q.front();
                q.pop();
                current = val.value;
                root = val.node;
                
                if (current < min) {
                    min = current;
                } else if (current > max) {
                    max = current;
                }
                
                values[current].push_back(val.node->val);
                
                if (root->left != NULL) {
                    q.push(NodeValue(root->left, current - 1));
                }
                
                if (root->right != NULL) {
                    q.push(NodeValue(root->right, current + 1));
                }
            }
        }
    };
    

Log in to reply
 

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