construct binary tree from preorder and postorder traversal leetcode | leetcode 889 | dfs

Показать описание

Problem Link - construct binary tree from preorder and postorder traversal leetcode | leetcode 889 | dfs

#Tree #DFS #Recursive #Coding #Programming #Interview #Practice #Leetcode #Problem_889 #Construct_Binary_Tree_from_Preorder_and_Inorder_Traversal #Algorithm #Java #Preparation

Рекомендации по теме

Комментарии

hello sir i used len = idx - preStart +1 but it is giving wrong ans intead of preStart if we use postStart it gives correct ans.can you please tell the reason behind this?

Iamnoone

working java code:
class Solution {
public TreeNode construct(int[] pre, int preStart, int preEnd, int[] post,
int postStart, int postEnd, HashMap<Integer, Integer> map) {
if(preStart > preEnd) return null;
TreeNode root = new TreeNode(pre[preStart]);
if(preStart == preEnd) return root; // when there is only one node in left or right subtree
int postIdx = postStart;

postIdx = map.get(pre[preStart+1]); // preStart+1 bcz we can determine left and right subtree nodes by checking the pos of next node in preOrder in postorder

int len = postIdx-postStart +1;
root.left = construct(pre, preStart+1, preStart+len, post, postStart, postIdx, map);
root.right = construct(pre, preStart+len+1, preEnd, post, postIdx+1, postEnd-1, map);
return root;
}

public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
HashMap<Integer, Integer> map = new HashMap<>();
int n = postorder.length;
for(int i = 0; i < n; i++) {
map.put(postorder[i], i); // indx, value
}

return construct(preorder, 0, n-1, postorder, 0, n-1, map);
}
}

anuragjaiswal

Thank you, it's amazing. I don't know why there are so many dislikes

sarthakgaba

working solution

unordered_map<int, int> mp;

TreeNode* solve(vector<int>& preorder, vector<int>& postorder, int preS, int preE, int postS, int postE){
if(preS>preE)
return NULL;
TreeNode* root = new TreeNode(preorder[preS]);

if(preS==preE)
return root;

int idx = mp[preorder[preS+1]];
idx++;
int numE = idx-postS+1;
root->left = solve(preorder, postorder, preS+1, preS+numE, postS, idx);
root->right = solve(preorder, postorder, preS+numE+1, preE, idx+1, postE-1);
return root;
}
TreeNode* preorder, vector<int>& postorder) {
int n=preorder.size();

for(int i=0; i<n; ++i){
mp[postorder[i]]=i;
}

return solve(preorder, postorder, 0, n-1, 0, n-1);
}

priyankaram

Why is it giving me runtime error?

TreeNode* preorder, vector<int>& postorder) {
unordered_map<int, int> index; //of postorder
for(int i=0;i<postorder.size();++i){
index[postorder[i]]=i;
}
return buildTreePrePost(preorder, 0, preorder.size()-1, postorder, 0, postorder.size()-1, index);
}
TreeNode* buildTreePrePost(vector<int>& preorder, int preS, int preE, vector<int>& postorder, int postS, int postE, unordered_map<int, int>& index){

if(preS>preE || postS>postE){
return NULL;
}
TreeNode* root=new TreeNode(preorder[preS]);
int postRoot=index[preS+1];
int numsLeft=postRoot-postS+1;
root->left=buildTreePrePost(preorder, preS+1, preS+numsLeft, postorder, postS, postRoot, index);
root->right=buildTreePrePost(preorder, preS+numsLeft+1, preE, postorder, postRoot+1, postE-1, index);
return root;
}

JohnWick-khow

Can you answer me one thing is it okay for someone if he is not able to solve some questions like i got stuck in this and then lookup for solution then solve?

anmolojha

construct binary tree from preorder and postorder traversal leetcode | leetcode 889 | dfs

Construct Binary Tree from Inorder and Preorder Traversal - Leetcode 105 - Python

5.9 Construct Binary Tree from Preorder and Postorder traversal | Data Structure Tutorials

Construct binary search tree from preorder traversal | Leetcode #1008

Leetcode - Construct Binary Search Tree from Preorder Traversal (Python)

Construct Binary Tree from Preorder and Postorder Traversal - Leetcode 889 - Python

LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal (Algorithm Explained)

Create Binary Tree from pre-order and in-order traversal (LeetCode 105) | Easiest explanation

Leetcode - Construct Binary Tree from Preorder and Inorder Traversal (Python)

Construct Binary Tree From Preorder And Inorder Traversal - LeetCode 105

L34. Construct a Binary Tree from Preorder and Inorder Traversal | C++ | Java

Construct Full Binary Tree From Preorder and Postorder traversal | Trees

L48. Construct a BST from a preorder traversal | 3 Methods

Preorder Binary Tree Traversal

Construct Binary Tree from Preorder and Inorder Traversal - 105 technical interview - Google, amazon

Constructing binary tree from inorder and preorder traversal || Data Structures

[Java] Leetcode 889. Construct Binary Tree from Preorder and Postorder Traversal [Binary Tree #17]

LEETCODE 105 (JAVASCRIPT) | CONSTRUCT BINARY TREE FROM PREORDER AND INORDER TRAVERSAL

Binary Tree Traversal : Inorder | #datastructure #datastructures #viral #shorts #short #shortsvideo

Lecture 66: Construct a Binary Tree from InOrder/PreOrder/PostOrder Traversal

Construct Binary Search Tree from Preorder Traversal | Leetcode 1008 | Live coding session 🔥🔥🔥...

LeetCode 889 Construct Binary Tree from Preorder and Postorder Traversal | Google Amazon

Construct Binary Tree from Preorder and Inorder Traversal | LeetCode 105 | Theory + Python

[Java] Leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal [Binary Tree #5]

Construct a Binary Tree Using Preorder and Postorder in Data Structure | Shortcut Trick