4ms simple solution, no advanced structure C++


  • 1
    K
    class Solution {
    public:
    vector<vector<int>> verticalOrder(TreeNode* root) {
        vector<vector<int> > result;
        if (!root) { return result; }
        int left_most = minPos(root, 0);
        int right_most = maxPos(root, 0);
        int Size = right_most - left_most + 1;
        result.reserve(Size);
        for (int i=0; i<Size; i++) {
            result.push_back(vector<int>{});
        }
            
        queue<TreeNode*> qt;
        queue<int> qp;
            
        qt.push(root);
        qp.push(-left_most);
            
        TreeNode* tmp_node;
        int tmp_pos;
        while (!qt.empty()) {
            tmp_node = qt.front();
            tmp_pos = qp.front();
            qt.pop();
            qp.pop();
            result[tmp_pos].push_back(tmp_node->val);
            if (tmp_node->left)  { 
                qt.push(tmp_node->left);  
                qp.push(tmp_pos-1);
            }
            if (tmp_node->right) { 
                qt.push(tmp_node->right); 
                qp.push(tmp_pos+1);
            }
        }
            
        return result;
    }
        
    int minPos(TreeNode* root, int pos) {
        if (!root) { return INT_MAX; }
        int left_min = minPos(root->left, pos-1);
        int right_min = minPos(root->right, pos+1);
        return min(pos, min(left_min,right_min));
    }
        
    int maxPos(TreeNode* root, int pos) {
        if (!root)  { return INT_MIN; }
        int left_max = maxPos(root->left, pos-1);
        int right_max = maxPos(root->right, pos+1);
        return max(pos, max(left_max, right_max));
    }
        
    };

Log in to reply
 

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