My simple c++ solution using distance to the root


  • 0
    K
    class Solution {
    public:
    void findDistance(TreeNode * root, int & minDt, int & maxDt, int distance){
        if(!root)return;
        if( distance < minDt)minDt=distance;
        else if(distance > maxDt)maxDt=distance;
        
        findDistance(root->left, minDt, maxDt, distance-1);
        findDistance(root->right, minDt, maxDt, distance+1);
    }
    vector<vector<int>> verticalOrder(TreeNode* root) {
        if(!root)return {};
        int min=0, max=0;
        vector<vector<int>>res;
        
        findDistance(root, min, max, 0);
        for(int i=min; i <=max; i++)res.push_back({});
        queue<TreeNode * >node;
        queue<int>distance;
        node.push(root);
        distance. push(-min);
        while(!node.empty()){
            TreeNode * cur=node.front();
            node.pop();
            int dist=distance.front();
            res[dist].push_back(cur->val);
            distance.pop();
            if(cur->left){
                node.push(cur->left);
                distance.push(dist - 1);
            }
            if(cur->right){
                node.push(cur->right);
                distance.push(dist + 1);
            }
        }
        return res;
    }
    };

Log in to reply
 

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