classTreeNode:def__init__(self,x):self.val=xself.left=Noneself.right=NoneclassSolution:defbuildTree(self,preorder:List[int],inorder:List[int])->TreeNode:ifnotpreorderornotinorder:returnNone# Find the rootroot=TreeNode(preorder[0])id=inorder.index(root.val)root.left=self.buildTree(preorder[1:id+1],inorder[0:id])root.right=self.buildTree(preorder[id+1:],inorder[id+1:])returnroot
Explanation
Preorder: root | left | right
Inorder: left | root | right
Root is the first element in preorder list.
Root in inorder list separates the left and right sub-trees.
Time Complexity: O(N)
Space Complexity: O(N)
Task 2 - Q16. 数值的整数次方
Question
实现 pow(x, n) ,即计算 x 的 n 次幂函数(即,xn)。不得使用库函数,同时不需要考虑大数问题。
Solution
1
2
3
4
5
6
7
8
9
10
classSolution:defmyPow(self,x:float,n:int)->float:ifn==0:return1elifn<0:return1/self.myPow(x,-n)# Make n from negative to positiveelifn&1==0:# Even or notreturnself.myPow(x*x,n>>1)# i.e. n//2. It ensures the result is an integer. else:returnx*self.myPow(x,n-1)