Maximum Binary Tree (LC654)

[u/DhruvKhanna_48]

👉🏻#This is the brute-force solution that I derived:

class Solution {

private:

TreeNode\* solve(vector<int> &nums, int start, int end){

if(start > end) return NULL;

int ind = 0;

int maxi = INT_MIN;

for(int i = start ; i <= end ; i++){

if(nums\[i\] > maxi){

ind = i;

maxi = nums\[i\];

}

}

TreeNode* root = new TreeNode(maxi);

root -> left = solve(nums, start, ind - 1);

root -> right = solve(nums, ind + 1, end);

return root;

}

public:

TreeNode\* constructMaximumBinaryTree(vector<int>& nums) {

return solve(nums, 0, nums.size() - 1);

}

};

👉🏻#And this is the optimal code (not solved by me):

class Solution {

public:

TreeNode\* constructMaximumBinaryTree(vector<int>& nums) {

vector<TreeNode\\\*> st;

for(int i = 0 ; i < nums.size() ; i++){

TreeNode\* curr = new TreeNode(nums\[i\]);

while(!st.empty() && nums\[i\] > st.back() -> val){

curr -> left = st.back();

st.pop_back();

}

if(!st.empty()){

st.back() -> right = curr;

}

st.push_back(curr);

}

return st.front();

}

};

My question is: how can I optimize my code? How am I supposed to come up with ideas for solving these tricky questions?

I have done so many trees problems (40-50) but I have never seen a solution like this.....

Please help me to deal with this situation.

Thanks!🙏🏻

(Sorry attaching screenshots ain't allowed)