C++ BFS Solution


  • 0
    J
    void getMaxLeftRight(TreeNode* root, int column, int &leftMax, int &rightMax) {
        if(!root) return;
        
        int l1 = 0, r1 = 0; getMaxLeftRight(root->left, column-1, l1, r1);
        int l2 = 0, r2 = 0; getMaxLeftRight(root->right, column+1, l2, r2);
        
        leftMax = min(column, min(l1, l2));
        rightMax = max(column, max(r1, r2));
    }
    
    vector<vector<int>> verticalOrder(TreeNode* root) {
        if(!root) 
            return vector<vector<int>>();
        
        TreeNode* t = root;
        int leftMax = 0, rightMax = 0;
        getMaxLeftRight(root, 0, leftMax, rightMax);
    
        vector<vector<int>> result (-leftMax+rightMax+1, vector<int>());
        queue<pair<TreeNode*, int>> q; q.push(make_pair(root, -leftMax));
    
    	while (!q.empty()) {
    		pair<TreeNode*, int> p = q.front(); q.pop();
    		result[p.second].push_back(p.first->val);
    
    		if (p.first->left) q.push(make_pair(p.first->left, p.second - 1));
    		if (p.first->right) q.push(make_pair(p.first->right, p.second + 1));
    	}
        
        return result;
    }

Log in to reply
 

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