Commit245ed81

authored

Merge pull requestneetcode-gh#258 from monkey-patcher/105-leetcode-fix

105-leetcode create binary tree from traversals/Use of dictionary

2 parentsca36cec +c964b9a commit245ed81Copy full SHA for 245ed81

File tree

+15

-8

lines changed

+15

-8

lines changed

Lines changed: 15 additions & 8 deletions

Original file line number	Diff line number	Diff line change
`@@ -1,10 +1,17 @@`
`1`	`1`	`classSolution:`
`2`	`2`	`defbuildTree(self,preorder:List[int],inorder:List[int])->Optional[TreeNode]:`
`3`		`-ifnotpreorderornotinorder:`
`4`		`-returnNone`
`5`		`-`
`6`		`-root=TreeNode(preorder[0])`
`7`		`-mid=inorder.index(preorder[0])`
`8`		`-root.left=self.buildTree(preorder[1:mid+1],inorder[:mid])`
`9`		`-root.right=self.buildTree(preorder[mid+1:],inorder[mid+1:])`
`10`		`-returnroot`
	`3`	`+inorder_index_mapping= {}`
	`4`	`+fork,vinenumerate(inorder):`
	`5`	`+inorder_index_mapping[v]=k`
	`6`	`+index=0`
	`7`	`+defbuildtree(left,right):`
	`8`	`+nonlocalindex`
	`9`	`+ifleft>right:`
	`10`	`+returnNone`
	`11`	`+root_val=preorder[index]`
	`12`	`+root=TreeNode(root_val)`
	`13`	`+index+=1`
	`14`	`+root.left=buildtree(left,inorder_index_mapping[root_val]-1)`
	`15`	`+root.right=buildtree(inorder_index_mapping[root_val]+1,right)`
	`16`	`+returnroot`
	`17`	`+returnbuildtree(0,len(preorder)-1)`

Comments

(0)