C++ easy understanding solution, use two 2D array + preOrder Travers


  • 0
    class Solution {
        vector<vector<int>> levelCheck;
        vector<vector<int>> result;
    public:
        void orderHelper(TreeNode* root, int left, int right, int& mid)
        {
            if(!root) return;
            int pos=0;
            if(left-right > 0) 
            {
                pos = mid-(left-right);
                if(pos < 0)
                {
                   vector<int> newArea={root->val};
                   result.insert(result.begin(), newArea);
                   vector<int> newLevel={left+right};
                   levelCheck.insert(levelCheck.begin(), newLevel);
                   mid++;
                }
                else 
                    updateLevelandResult(root, left+right, pos);
            }   
            else //if(right-left >=0)
            {
                pos = mid+(right-left);
                if(pos >= result.size())
                {
                    vector<int> newArea={root->val};
                    result.push_back(newArea);
                    vector<int> newLevel={left+right};
                    levelCheck.push_back(newLevel);
                }
                else
                    updateLevelandResult(root, left+right, pos);
            }    
            orderHelper(root->left, left+1, right, mid);
            orderHelper(root->right, left, right+1, mid);
        }
        void updateLevelandResult(TreeNode* root, int level, int pos)
        {
            auto it = upper_bound(levelCheck[pos].begin(), levelCheck[pos].end(), level);
            int step = it-levelCheck[pos].begin();
            result[pos].insert(result[pos].begin()+step, root->val);
            levelCheck[pos].insert(levelCheck[pos].begin()+step, level);  
        }
        vector<vector<int>> verticalOrder(TreeNode* root) {
            int mid=0;
            orderHelper(root, 0, 0, mid);
            return result;
        }
    };

Log in to reply
 

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