654.最大二叉树
1、使用切片
class Solution:
def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
if len(nums) == 0:
return None
max_val = max(nums)
max_index = nums.index(max_val)
node = TreeNode(max_val)
node.left = self.constructMaximumBinaryTree(nums[:max_index])
node.right = self.constructMaximumBinaryTree(nums[max_index+1:])
return node
2、基础版
class Solution:
def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
if len(nums) == 1:
return TreeNode(nums[0])
max_val = 0
max_index = 0
for i in range(len(nums)):
if nums[i] > max_val:
max_val = nums[i]
max_index = i
node = TreeNode(max_val)
if max_index > 0:
node.left = self.constructMaximumBinaryTree(nums[:max_index])
if max_index < len(nums) - 1:
node.right = self.constructMaximumBinaryTree(nums[max_index+1:])
return node
3、下标法
class Solution:
def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
return self.buildTree(nums, 0, len(nums))
def buildTree(self, nums, left, right):
if left >= right:
return None
max_val = nums[left]
max_index = left
for i in range(left+1, right):
if nums[i] > max_val:
max_val = nums[i]
max_index = i
node = TreeNode(max_val)
node.left = self.buildTree(nums, left, max_index)
node.right = self.buildTree(nums, max_index+1, right)
return node
617.合并二叉树
1、前序遍历
class Solution:
def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
if not root1:
return root2
if not root2:
return root1
node = TreeNode(root1.val+root2.val)
node.left = self.mergeTrees(root1.left, root2.left)
node.right = self.mergeTrees(root1.right, root2.right)
return node
2、迭代法
from collections import deque
class Solution:
def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
if not root1 and not root2:
return None
if not root1:
return root2
if not root2:
return root1
queue = deque()
queue.append(root1)
queue.append(root2)
while queue:
node1 = queue.popleft()
node2 = queue.popleft()
if node1.left and node2.left:
queue.append(node1.left)
queue.append(node2.left)
if node1.right and node2.right:
queue.append(node1.right)
queue.append(node2.right)
node1.val = node1.val + node2.val
if not node1.left and node2.left:
node1.left = node2.left
if not node1.right and node2.right:
node1.right = node2.right
return root1
1、递归法
class Solution:
def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if root is None:
return None
if root.val == val:
return root
if root.val > val:
return self.searchBST(root.left, val)
else:
return self.searchBST(root.right, val)
2、迭代法
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
98.验证二叉搜索树
思路: 二叉搜索树的中序遍历是递增的
1、设定最大的极小值递归法
class Solution:
def __init__(self):
self.max_val = float('-inf')
def isValidBST(self, root: Optional[TreeNode]) -> bool:
if root is None:
return True
left = self.isValidBST(root.left)
if self.max_val < root.val:
self.max_val = root.val
else:
return False
right = self.isValidBST(root.right)
return left and right
2、记录前一个节点的递归法
class Solution:
def __init__(self):
self.pre = None # 记录前一个节点
def isValidBST(self, root: Optional[TreeNode]) -> bool:
if root is None:
return True
left = self.isValidBST(root.left)
if self.pre and self.pre.val >= root.val:
return False
self.pre = root
right = self.isValidBST(root.right)
return left and right
3、迭代法
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
if root is None:
return True
stack = []
res = []
cur, pre = root, None # cur指向跟节点，pre 记录前一个节点
while cur or stack:
if cur:
stack.append(cur)
cur = cur.left
else:
cur = stack.pop()
if pre and pre.val >= cur.val:
return False
pre = cur
cur = cur.right
return True