654. 最大二叉树 - 力扣（LeetCode）
image.png
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
if not nums:
return None
max_num = max(nums)
max_index = nums.index(max_num)
node = TreeNode(val=max_num)
node.left = self.constructMaximumBinaryTree(nums[:max_index])
node.right = self.constructMaximumBinaryTree(nums[max_index+1:])
return node
- 递归要有变量接return
617. 合并二叉树 - 力扣（LeetCode）
image.png
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
if root1 == None: return root2
if root2 == None: return root1
root1.val += root2.val
root1.left = self.mergeTrees(root1.left, root2.left)
root1.right = self.mergeTrees(root1.right, root2.right)
return root1
700. 二叉搜索树中的搜索 - 力扣（LeetCode）
image.png
解题思路
注意是二叉搜索树
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
# 迭代法
class Solution:
def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
while root:
if root.val > val:
root = root.left
elif root.val < val:
root = root.right
else:
return root
return None
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
# 递归法
class Solution:
def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if not root or root.val == val:
return root
if root.val < val:
result = self.searchBST(root.right, val)
if root.val > val:
result = self.searchBST(root.left, val)
return result
98. 验证二叉搜索树 - 力扣（LeetCode）
image.png
解题思路
利用中序遍历，如果是二叉搜索树，遍历结果应该是单调递增的
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
# 中序遍历就是递增序列了，定义全局最小值
class Solution:
def __init__(self):
self.max_value = float('-inf')
def isValidBST(self, root: Optional[TreeNode]) -> bool:
if root == None:
return True
left_bool = self.isValidBST(root.left)
if root.val > self.max_value:
self.max_value = root.val
else:
return False
right_bool = self.isValidBST(root.right)
return left_bool&right_bool
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
# 中序遍历就是递增序列了，利用双指针，避免第一个节点值就是float最小值
class Solution:
def __init__(self):
self.pre = TreeNode(val=None)
def isValidBST(self, root: Optional[TreeNode]) -> bool:
if root == None:
return True
left_bool = self.isValidBST(root.left)
if self.pre.val != None and root.val <= self.pre.val:
return False
self.pre = root
right_bool = self.isValidBST(root.right)
return left_bool&right_bool
- 注意两种不同方法中 ‘中’的条件判断的不同
