C++ solution using only vectors


  • 0
    S
    /**
     * 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) {
            if (root==NULL) return vector<vector<int>>();
            
            int index = 0, lower = 0, upper = 0;
            vector<TreeNode*> visit = {root};
            vector<int> offset = {0};
    
            while (index != visit.size()) {
                if (visit[index]->left!=NULL) {
                    visit.push_back(visit[index]->left);
                    offset.push_back(offset[index]-1);
                    if (offset[index]-1<lower) lower = offset[index]-1;
                }
                if (visit[index]->right!=NULL) {
                    visit.push_back(visit[index]->right);
                    offset.push_back(offset[index]+1);
                    if (offset[index]+1>upper) upper = offset[index]+1;
                }
                ++index;
            }
            
            vector<vector<int>> val = vector<vector<int>>(upper-lower+1,vector<int>());
            for (int i=0; i<visit.size(); ++i) {
                val[offset[i]-lower].push_back(visit[i]->val);
            }
            return val;
        }
    };

Log in to reply
 

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