算法打卡day17

今日任务：

1）654.最大二叉树

2）617.合并二叉树

3）700.二叉搜索树中的搜索

4）98.证二叉搜索树

654.最大二叉树

题目链接：654. 最大二叉树 - 力扣（LeetCode）

给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：
1.二叉树的根是数组中的最大元素。
2.左子树是通过数组中最大值左边部分构造出的最大二叉树。
3.右子树是通过数组中最大值右边部分构造出的最大二叉树。

通过给定的数组构建最大二叉树，并且输出这个树的根节点。

输入:[3,2,1,6,0,5]
输出:返回下面这棵树的根节点:
[6,3,5,None,2,0,None,None,1]

文章讲解：代码随想录 (programmercarl.com)

视频讲解：又是构造二叉树，又有很多坑！| LeetCode：654.最大二叉树哔哩哔哩bilibili

思路：

很明显这题采用深度优先遍历算法（DFS）中的前序遍历

1)首先找出列表中的最大数作为根节点

2)最大数左边列表作为左子树，最大数右边列表作为右子树。

3)将左右列表作为新列表，重复1）-2）步

4）返回根节点

这里第三步就是开始递归了，那我们需要明确递归函数的参数与返回值，明确递归函数的终止条件，递归函数的单层逻辑

终止条件：当列表的大小为1时，也就是列表中只有一个树，直接将这个树作为当前递归中的根节点即可返回当前节点（从整体上看，起始这个节点应该是一个叶子节点）

单层递归逻辑：遍历列表找出列表最大值，并从最大值拆分成左右子树区间

递归函数参数与返回值：参数肯定要传入区间，返回值返回当前递归层中的根节点

# Definition for a binary tree node.
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightclass Solution:def constructMaximumBinaryTree(self, nums: list[int]) -> Optional[TreeNode]:if not nums:returnnum_size = len(nums)if num_size == 1:return TreeNode(nums[0])# 找最大值索引max_index = 0for i in range(num_size):if nums[i] > nums[max_index]:max_index = inode = TreeNode(nums[max_index])  # 中node.left = self.constructMaximumBinaryTree(nums[:max_index])  # 左node.right = self.constructMaximumBinaryTree(nums[max_index + 1:])  # 右return node

根据上面的思路，我写出来最直白的代码就是这样，比较好理解，还有一些改进的空间。

我是用力扣上给出的这个函数作为递归函数，所以其传参与返回值就固定了。而我们传参时使用切片，会浪费内存开销。我们可以重新定义一个递归函数，传参改为传入列表起始和终止，这样我们操作的就是一个列表，而不是每次递归重新创建列表。

# Definition for a binary tree node.
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = right# 改进，不使用切片，会额外浪费内存开销，采用传入列表起始终止索引
class Solution2:def constructMaximumBinaryTree(self, nums: list[int]) -> Optional[TreeNode]:if not nums:returnreturn self.traversal(nums, 0, len(nums))def traversal(self, nums: list[int], left: int, right: int):if left >= right:returnmax_index = leftfor i in range(left + 1, right):if nums[i] > nums[max_index]:max_index = inode = TreeNode(nums[max_index])node.left = self.traversal(nums, left, max_index)node.right = self.traversal(nums, max_index + 1, right)return node

617.合并二叉树

题目链接：617. 合并二叉树 - 力扣（LeetCode）

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1：
输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]

示例 2：
输入：root1 = [1], root2 = [1,2]
输出：[2,2]

文章讲解：代码随想录 (programmercarl.com)

视频讲解：一起操作两个二叉树？有点懵！| LeetCode：617.合并二叉树哔哩哔哩bilibili

思路：

我们可以采用深度优先遍历（DFS）中的前序遍历，

1）两棵树同时开始遍历，判断两棵树根节点是否为空，若一个为空，则返回另一个，连个都为空，也是返回空

2）当两个节点不为空时，则相加，我们可以创建新树记录，也可以在原树上修改

3）重复1）-2），继续比较两个树根节点的左节点，右节点

4）返回合并后的根节点

递归的终止：但凡有一个节点为空, 就立刻返回另外一个. 如果另外一个也为None就直接返回None.

单层递归逻辑：当两个节点均不为空时，继续比较其左右节点

递归函数的参数和返回值：用力扣给的函数作为递归函数，参数和返回值已经固定了

class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = right
class Solution:def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:# 递归终止条件:#  但凡有一个节点为空, 就立刻返回另外一个. 如果另外一个也为None就直接返回None.if not root1:return root2if not root2:return root1# 上面的递归终止条件保证了代码执行到这里root1, root2都非空.root1.val += root2.val  # 中root1.left = self.mergeTrees(root1.left, root2.left)  # 左root1.right = self.mergeTrees(root1.right, root2.right)  # 右return root1  # ⚠️ 注意: 本题我们重复使用了题目给出的节点而不是创建新节点. 节省时间, 空间.

700.二叉搜索树中的搜索

题目链接：700. 二叉搜索树中的搜索 - 力扣（LeetCode）

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。返回以该节点为根的子树。如果节点不存在，则返回 null 。

一个二叉搜索树具有如下特征：

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

示例 1:
输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]

示例 2:
输入：root = [4,2,7,1,3], val = 5
输出：[]

文章讲解：代码随想录 (programmercarl.com)

视频讲解：不愧是搜索树，这次搜索有方向了！| LeetCode：700.二叉搜索树中的搜索哔哩哔哩bilibili

思路：

根据搜索二叉树的定义，这题比较好做，我们只需要从上到下遍历

当目标值等于当前节点值，我们则直接返回这个节点即可

当目标值大于当前节点值，我们则往右子树找

当目标值小于当前节点值，我们则往左子树找

class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightclass Solution:def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:# 终止if not root or root.val == val:return rootif root.val>val:return self.searchBST(root.left,val)if root.val<val:return self.searchBST(root.right,val)

这题也可以使用迭代法实现深度优先遍历，因为搜索树结构的特殊性（中序遍历节点的有序性），不需要回溯。代码如下：

class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightclass Solution:def searchBST(self, root: TreeNode, val: int) -> TreeNode:while root:if val < root.val:root = root.leftelif val > root.val:root = root.rightelse:return rootreturn None

感想：不同二叉树都有其结构特性，要多熟悉其结构特性

98.验证二叉搜索树

题目链接：98. 验证二叉搜索树 - 力扣（LeetCode）

文章讲解：代码随想录 (programmercarl.com)

视频讲解：你对二叉搜索树了解的还不够！ | LeetCode：98.验证二叉搜索树哔哩哔哩bilibili

思路：

如果给一个搜索二叉树，我们中序遍历出来的顺序是一个单调递增的

中序遍历：234567

所以最简单直接的方法是，将二叉树采用中序遍历出来，用数组存储，然后遍历数组后一位是否大于前一位。

这里我们可以不用数组，在遍历的过程中就将上一个节点用变量存储起来，当遍历到下一个节点时，比较其是否大于上一个节点即可。如果小直接返回False，如果大则继续

class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightclass Solution:def __init__(self):self.max_val = float('-inf')def isValidBST(self, root: Optional[TreeNode]) -> bool:if not root:return True# 左left = self.isValidBST(root.left)# 中if root.val > self.max_val:self.max_val = root.valelse:return False# 右right = self.isValidBST(root.right)return left and right

这里存储上一个节点的变量max_val，我们设为了float('-inf')，没有用int('-inf')，是因为测试案例中存在节点的值为int('-inf')，那我们就不能拿这个去比较，所以我采用了float('-inf')，但是这样也有一个问题，当测试案例中出现最小值为float('-inf')，我们这个代码也会报错，所以接下来我们做了一点调整

# 改进
class Solution2:def __init__(self):self.pre = Nonedef isValidBST(self, root: Optional[TreeNode]) -> bool:if not root:return True# 左left = self.isValidBST(root.left)# 中if self.pre is not None and self.pre >= root.val:return Falseelse:self.pre = root.val# 右right = self.isValidBST(root.right)return left and right

这里有坑，第一反应判空时，if self.pre即表示其不为空，但是我们这self.pre存放的是数值！！当self.pre=0时也会跳过