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

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

July 2020 Leetcode Challenge
Leetcode - Construct Binary Tree from Inorder and Postorder Traversal

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

Комментарии

aye yai yai....i hate these problems

thanks tim!

EDIT: Also, I think it was really great when you were explaining the recusrive call, you left the base condition to be filled out later, but just created the body of the helper first. It helps me out too because I pause every few seconds to try to see if I can code out what you do! Thanks man!

janmichaelaustria

Best and the easiest solution out there. Thanks!

siddharthsingh

I have a question on it. Why I got an error message with "if inorder ==None or postorder == None"?

lucylu

how do you come up with these types of solutions ? is there any book which even I can reference?

siddharthsingh

Here is what was my first attempt at an iterative version, that ended up timing out on large input size! Can you guess the time complexity? xD

def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:

head = TreeNode(postorder[-1])
for x in reversed(postorder[:-1]):
curr = head
y = 0
while True:
if inorder[y] == curr.val:
if curr.right is None:
curr.right = TreeNode(x)
break
else:
curr = curr.right
y = 0
elif inorder[y] == x:
if curr.left is None:
curr.left = TreeNode(x)
break
else:
curr = curr.left
y = 0
else:
y += 1
return head

scullyy

Shouldn't the Space Complexity be O(N) as we are creating a mapper?

jadhavswapnil

Best solution I have seen on this problem.. Thanks

sharifmansuri

Hello why root.right is before root.left?

Iamnoone

Here is a different approach that uses a more intuitive recursion:

miteshkumar

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

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

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

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

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

Construct Binary Tree From Preorder And Inorder Traversal - LeetCode 105

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

construct binary tree from preorder and inorder traversal leetcode | leetcode 105 | binary tree

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

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

Construct Binary Tree from Inorder and Postorder Traversal | Day 27 | July [ Leetcode - 106 ]

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

Convert Sorted Array to Binary Search Tree - Leetcode 108 - Python

LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal [Solution + Code Explained ]

construct binary tree from inorder and postorder traversal leetcode | leetcode 106 | binary tree

Construct binary search tree from preorder traversal | Leetcode #1008

Construct String from Binary Tree - Leetcode 606 - Python

[Java] Leetcode 106. Construct Binary Tree from Inorder and Postorder Traversal [Binary Tree #7]

Разбор задачи 105 leetcode.com Construct Binary Tree from Preorder and Inorder Traversal. C++...

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

LeetCode 1008. Construct Binary Search Tree from Preorder Traversal

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

Construct Binary Tree from Inorder and Postorder Traversal | Leetcode 106

106. Construct Binary Tree from Inorder and Postorder Traversal | LeetCode daily | C++

LeetCode 536. Construct Binary Tree from String