Construct Binary Tree from Inorder and Postorder Traversal - Leetcode 106 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
7:45 - Coding Explanation

leetcode 106

#neetcode #leetcode #python

[ancai]

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<int>& v, int val) {
for (int i = 0; i < v.size(); i++) {
if (v[i] == val) {
return i;
}
}

// not found
return -1;
}

TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
return dfs(inorder, postorder, 0, inorder.size() - 1);
}

TreeNode *dfs(const vector<int>& inorder, vector<int>& 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;
}

[yang]

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.

[name_surname_]

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

[shepmax]

Or just solve it recursively without extra memory like 105:

if not inorder or not postorder:
return None

root = TreeNode(postorder[-1]) # Last element in postorder is the root
idx = inorder.index(postorder[-1]) # Find root in inorder traversal

# Correcting the left subtree postorder slice
root.left = self.buildTree(inorder[:idx], postorder[:idx])
root.right = self.buildTree(inorder[idx + 1:], postorder[idx:-1])

return root

[shuyinlam]

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.

[ishtiaqueahmed]

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

[דניאלאביב-ות]

what software are u using to draw on the screen?

[Dhanushh]

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.

[MP-nyep]

Awesome explanation as always . Thank you

[yang]

class Solution {
List<Integer> list = new ArrayList();
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
public TreeNode buildTree(int[] inorder, int[] postorder) {
for (int p : postorder)
list.add(0, p);

for (int i=0;i<inorder.length;i++)
map.put(inorder[i], i);
return dfs(0, inorder.length-1);
}
TreeNode dfs(int l, int r) {
if ( l > 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;
}
}

[firezdog]

Nice now do one on the iterative solution with stack 😉

[TheHyxD]

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!

[patrickfeeney]

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<Integer, Integer> inorderIdx = new HashMap<>();
for (int i = 0; i < inorder.length; 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<Integer, Integer> inorderIdx, int[] postorderIdxEnd) {
if (leftIdx > rightIdx) return null;

TreeNode root = new

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.

[uniquename]

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?

[itsokayben]

how come this is a different channel??

[muzaffartursunov]

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!

[kimayapanash]

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

[justine-george]

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

[stefanopalmieri]

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