当前位置：首页 > news >正文

算法训练营day17 654.最大二叉树、617.合并二叉树、700.二叉搜索树中的搜索、98.验证二叉搜索树

news 2025/7/15 15:16:36

二叉树第五篇博客加油！继续递归

654.最大二叉树

构造树一般采用的是前序遍历，因为先构造中间节点，然后递归构造左子树和右子树。

确定递归函数的参数和返回值

参数传入的是存放元素的数组，返回该数组构造的二叉树的头结点，返回类型是指向节点的指针。

确定终止条件

题目中说了输入的数组大小一定是大于等于1的，所以我们不用考虑小于1的情况，那么当递归遍历的时候，如果传入的数组大小为1，说明遍历到了叶子节点了。那么应该定义一个新的节点，并把这个数组的数值赋给新的节点，然后返回这个节点（即最后一个节点，同时递归结束）。

确定单层递归的逻辑

这里有三步工作

先要找到数组中最大的值和对应的下标，最大的值构造根节点，下标用来下一步分割数组。
最大值所在的下标左区间构造左子树这里要判断maxValueIndex > 0，因为要保证左区间至少有一个数值。
最大值所在的下标右区间构造右子树判断maxValueIndex < (nums.size() - 1)，确保右区间至少有一个数值。

# 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 len(nums) == 1:return TreeNode(nums[0])# 退出node = TreeNode(0)maxValue = 0maxValueIndex = 0for i in range(len(nums)):if nums[i] > maxValue:maxValue = nums[i]maxValueIndex = i node.val = maxValue# 以上是找到最大值、最大值的下标、构建的节点的valif maxValueIndex > 0: # 最大值不在最左边new_list = nums[:maxValueIndex]node.left = self.constructMaximumBinaryTree(new_list)if maxValueIndex < len(nums) - 1:# 最大值不在最右边new_list = nums[maxValueIndex + 1:]node.right = self.constructMaximumBinaryTree(new_list)return node # 这个位置很重要# 考虑三个点, 当前节点val、左孩子、右孩子'''# 使用切片if not nums:return Nonemax_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'''      '''class Solution:def traversal(self, nums: List[int], left: int, right: int) -> TreeNode:if left >= right:return NonemaxValueIndex = leftfor i in range(left + 1, right):if nums[i] > nums[maxValueIndex]:maxValueIndex = iroot = TreeNode(nums[maxValueIndex]) # 在数组的使用上做优化root.left = self.traversal(nums, left, maxValueIndex)root.right = self.traversal(nums, maxValueIndex + 1, right)return rootdef constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:return self.traversal(nums, 0, len(nums))    '''

注意类似用数组构造二叉树的题目，每次分隔尽量不要定义新的数组，而是通过下标索引直接在原数组上操作，这样可以节约时间和空间上的开销。

617.合并二叉树

最简单的方法其实是使用队列进行层序遍历，但是问题在于none节点上的数字应该怎么一一对应存储，如何写结束的逻辑呢？因为空节点不会自动结束——答案是若存在空节点，可以直接带入另一个数现存的节点，直接接上就好（对于指针的理解）

看了答案之后——同时遍历两个二叉树，和遍历一个树逻辑是一样的，只不过传入两个树的节点，同时操作。

确定递归函数的参数和返回值：

首先要合入两个二叉树，那么参数至少是要传入两个二叉树的根节点，返回值就是合并之后二叉树的根节点。

确定终止条件：

因为是传入了两个树，那么就有两个树遍历的节点t1 和 t2，如果t1 == NULL 了，两个树合并就应该是 t2 了，注意这个位置是指针，所以“一劳永逸”（如果t2也为NULL也无所谓，合并之后就是NULL）。

确定单层递归的逻辑：

这里我们重复利用一下t1这个树，t1就是合并之后树的根节点（就是修改了原来树的结构）。单层递归中，就要把两棵树的元素加到一起。

递归——前序（递归的判断是基于后续递归的）

# 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 not root1:return root2 # 这个位置很关键, 要理解if not root2:return root1root1.val += root2.valroot1.left = self.mergeTrees(root1.left, root2.left)root1.right = self.mergeTrees(root1.right, root2.right)return root1

迭代

很巧妙的迭代，同时出入队列一对

# 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 not root1:return root2if not root2:return root1queue = collections.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 += node2.val # 相加逻辑if not node1.left and node2.left:# 这个位置很关键node1.left = node2.leftif not node1.right and node2.right:# 因为返回的是root1, 所以只需要判断root1为空的时候node1.right = node2.rightreturn root1

700.二叉搜索树中的搜索

这个题很简单，唯一能学习到的其实只有二叉搜索树的定义

有效二叉搜索树定义如下：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

递归

# 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 # 没找到root, 可以直接返回空# 为什么要有返回值: # 因为搜索到目标节点就要立即return，# 这样才是找到节点就返回（搜索某一条边），如果不加return，就是遍历整棵树了。if root.val > val:return self.searchBST(root.left, val)if root.val < val:return self.searchBST(root.right, val)

迭代

# 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 val < root.val:root = root.leftelif val > root.val:root = root.rightelse: return rootreturn None

98.验证二叉搜索树

背景问题注意：

陷阱1

不能单纯的比较左节点小于中间节点，右节点大于中间节点就完事了。

陷阱2

样例中最小节点可能是int的最小值，如果这样使用最小的int来比较也是不行的。此时可以初始化比较元素为longlong的最小值。进一步将，可以直接找到最左侧数值（同时为最小值），以该值进行后续比较

递归法（版本一）利用中序递增性质，转换成数组

要知道中序遍历下，输出的二叉搜索树节点的数值是有序序列。有了这个特性，验证二叉搜索树，就相当于变成了判断一个序列是不是递增的了

# 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 isValidBST(self, root: Optional[TreeNode]) -> bool:self.vec = []self.traversal(root)for i in range(1,len(self.vec)):if self.vec[i] <= self.vec[i - 1]: # 不允许存在相同点, 存在即返回错误！return Falsereturn Truedef traversal(self, root):if root is None:returnself.traversal(root.left)self.vec.append(root.val)self.traversal(root.right)

递归法（版本二）设定极小值，进行比较

因为二叉搜索树的中序遍历是一个从小到大的过程

# 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.maxVal = float('-inf')def isValidBST(self, root: Optional[TreeNode]) -> bool:if root is None:return Trueleft = self.isValidBST(root.left)# 顺序保证中序遍历if self.maxVal < root.val:self.maxVal = root.valelse:return Falseright = self.isValidBST(root.right)return left and right
'''class Solution:def __init__(self):self.pre = None  # 用来记录前一个节点def isValidBST(self, root):if root is None:return Trueleft = self.isValidBST(root.left)# 这里不要有空判断if self.pre is not None and self.pre.val >= root.val:return Falseself.pre = root  # 记录前一个节点, 用于下次比较right = self.isValidBST(root.right)return left and right
'''

迭代法

这个迭代法较为困难，感觉还是优先使用递归吧

# 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 isValidBST(self, root: Optional[TreeNode]) -> bool:stack = []cur = rootpre = Nonewhile cur is not None or len(stack) > 0:if cur is not None:stack.append(cur)cur = cur.left  # 左侧优先else:cur = stack.pop() # 左->中->右, 这个顺序要好好理解if pre is not None and cur.val <=pre.val:return Falsepre = curcur = cur.rightreturn True

查看全文

http://www.lryc.cn/news/588466.html