654 最大二叉树
class Solution:
def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
def sub(l,r):
if l>r:
return None
m=l
for i in range(l,r+1):
if nums[i]>nums[m]:
m=i
ret=TreeNode(nums[m])
ret.left=sub(l,m-1)
ret.right=sub(m+1,r)
return ret
return sub(0,len(nums)-1)
617 合并二叉树
def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
if not root1 and not root2:
return None
if root1 and root2:
root1.val+=root2.val
if not root1:
return root2
if not root2:
return root1
root1.left =self.mergeTrees(root1.left,root2.left)
root1.right =self.mergeTrees(root1.right,root2.right)
return root1
700 二叉搜索树中的搜索
def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
if not root1 and not root2:
return None
if root1 and root2:
root1.val+=root2.val
if not root1:
return root2
if not root2:
return root1
root1.left =self.mergeTrees(root1.left,root2.left)
root1.right =self.mergeTrees(root1.right,root2.right)
return root1
98 验证二叉搜索树
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def sub(root, ma=float('inf'), mi=float('-inf')):
if not root:
return True
v=root.val
if v<=mi or v>=ma:
return False
if not sub(root.left,v,mi) or not sub(root.right,ma,v):
return False
return True
return sub(root)
