The fact that Java passed primitive-arrays-by-value instead of by-reference messed me up for HOURS when I was trying to get your n^2 solution to work. Python handles the postorder array as reference, so every time it popped, it popped globally.

@murike

3 ай бұрын

What do you mean? Java primitive arrays are always pass by reference as any objects.

@graydenhormes5829

2 ай бұрын

@@murike They may have reassigned the reference provided by the method parameter. In java this doesn't change the value pointed to by the reference, it just changes what the reference points to.

The most tricker part of this issue, is regarding the sequence when we recursively called the helper or dfs function. As mentioned in the video, the second to last element is always the right subtree's root node if there's any. So when we write the recursive call, we should put the root->right = dfs(...) ahead of the root->left. Here is the C++ version w/o cache: int indexOfArray(const vector& v, int val) { for (int i = 0; i if (v[i] == val) { return i; } } // not found return -1; } TreeNode* buildTree(vector& inorder, vector& postorder) { return dfs(inorder, postorder, 0, inorder.size() - 1); } TreeNode *dfs(const vector& inorder, vector& postorder, int left, int right) { if (left > right) { return nullptr; } int rootVal = postorder.back(); postorder.pop_back(); int loffset = indexOfArray(inorder, rootVal); TreeNode *root = new TreeNode(rootVal); // second to last is always the right subtree's root node. root->right = dfs(inorder, postorder, loffset + 1, right); root->left = dfs(inorder, postorder, left, loffset - 1); return root; }

thank you, your solutions are much better than the official ones

Awesome explanation as always . Thank you

thank you so much. Just used this for my final exam!!

Best explanation 😊

Great vid chief

For reference, here is neetcode 105: kzread.info/dash/bejne/m5yelquKd72YqsY.html

what software are u using to draw on the screen?

It may look like the postorder sequence remain the same for right and left subtree callings but don't fall for it. The postorder sequence changes after you call the right subtree calling. You pass a different postorder sequence in left subtree calling. And you need to maintain a global postorder sequence Personally I feel how you determine the postorder sequence on calling right and left subtree is crucial aspect of this problem but often dismissed in many explanations I have seen.

Nice now do one on the iterative solution with stack 😉

Hey! Thank you for the video explanation, I finally understood how to do it recursively which is really easy. I have a suggestion, could you please not shorten code as you did on the 9th line? I think I understand what it does, however I am not really a Python developer and don't use one line expressions, so it's kinda hard to understand when someone does, especially in a tutorial. Thank you again!

I think you need to explain the reason why should the right subtree be processed before the left subtree. This does not sound obvious at all until it cannot find index in inorder when postorder fails to play catch up.

@jointcc2

Жыл бұрын

agree, and I think this is only specific to the case when you are given inorder and postorder

@Dhanushh

11 ай бұрын

can you please elaborate more on why we should not start with constructing left subtree? when postorder fails to play catch up?

@gilesgames8860

5 ай бұрын

It seems like you can start with left if you just slice both arrays, similar to how neetcode solved 105

@jnayehsirine6222

13 күн бұрын

there is no intuition behind , the simple reason is , when right exist and is not null , it will be always n-2 in postorder thats why u start with right

class Solution { List list = new ArrayList(); Map map = new HashMap(); public TreeNode buildTree(int[] inorder, int[] postorder) { for (int p : postorder) list.add(0,p); for (int i=0;i r ) return null; TreeNode node = new TreeNode( list.remove(0) ); int i = map.get(node.val); node.right = dfs(i+1,r ); node.left = dfs(l,i-1); return node; } }

plz do this in c++

This is how I did it in Java with your way of doing it: ```Java class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { int[] postorderIdxEnd = new int[] { postorder.length - 1 }; HashMap inorderIdx = new HashMap(); for (int i = 0; i inorderIdx.put(inorder[i], i); } return helper(0, inorder.length - 1, postorder, inorderIdx, postorderIdxEnd); } public TreeNode helper(int leftIdx, int rightIdx, int[] postorder, HashMap inorderIdx, int[] postorderIdxEnd) { if (leftIdx > rightIdx) return null; TreeNode root = new TreeNode(postorder[postorderIdxEnd[0]--]); int idx = inorderIdx.get(root.val); root.right = helper(idx + 1, rightIdx, postorder, inorderIdx, postorderIdxEnd); root.left = helper(leftIdx, idx - 1, postorder, inorderIdx, postorderIdxEnd); return root; } } ``` I used a single element array for the postorderIdxEnd so that the value would not change when popping back out form recursion since it's being passed as an argument.

I thought when we call two times recursive function the time complexity would be O(2^n) why it's O(n^2) in this case?

@pudgewars6447

Жыл бұрын

Do you still need the answer?

@uniquename2386

Жыл бұрын

@@pudgewars6447 Hey, probably not. Now I see that his O(n) recursive sol. just traverses the array, and in the case of O(n^2) he just finds an index which is O(n) also.

@pudgewars6447

Жыл бұрын

@@uniquename2386 Okay , good to see you .

@vijethkashyap151

5 ай бұрын

​@@pudgewars6447hey care to explain? I don't get how is O(n²)

@vijethkashyap151

5 ай бұрын

Is this right? This operation takes linear time (O(n)) in the worst case. For each node, it needs to scan the entire inorder list to find the index of the root node's value. This happens at every level of the recursion, leading to a total of O(n * n) = O(n^2) time complexity.

how come this is a different channel??

Wouldn't this be easier? class Solution: def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]: if not inorder or not postorder: return None root = TreeNode(postorder[-1]) mid = inorder.index(root.val) root.left = self.buildTree(inorder[:mid], postorder[:mid]) root.right = self.buildTree(inorder[mid + 1:], postorder[mid:len(postorder) - 1]) return root

@nitinpendekanti30

24 күн бұрын

The slicing and the index function make it an O(n^2) worst case doing this method. Neetcode's solution is more optimal

Hello! kzread.info/dash/bejne/qKFqlaquebidm9o.html Could you please explain why you declare "root.right" first and not "root.left". In my case i changed order of them like "root.left" comes first and "root.right" comes next. However, it did not work. It is working only your case. Thank you in advance!

Please teach us how to construct a file system like in windows in reactjs I asked another KZreadr and he gave an incomplete solution and stated that he cant solve the problem I really wanna learn it

@user-le6ts6ci7h

Жыл бұрын

N-ary tree , or trie

You should avoid modifying the input parameters. If I was your interviewer, I would dock you for that.

best solution