Day 17 卡玛笔记

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

1. 创建一个根节点，其值为 nums 中的最大值。
2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums 构建的 最大二叉树 。

示例 1：

输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。- [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。- 空数组，无子节点。- [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。- 空数组，无子节点。- 只有一个元素，所以子节点是一个值为 1 的节点。- [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。- 只有一个元素，所以子节点是一个值为 0 的节点。- 空数组，无子节点。

示例 2：

输入：nums = [3,2,1]
输出：[3,null,2,null,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])# 递归逻辑# 找最大值max_val=max(nums)root=TreeNode(max_val)# 最大值索引index=nums.index(max_val)# 左数组left_nums=nums[:index]# 右数组right_nums=nums[index+1:]# 如果左数组个数大于1才能递归if len(left_nums)>=1:left_child=self.constructMaximumBinaryTree(left_nums)root.left=left_child# 如果左数组没有元素则指向空，其实本来就默认指向空，这里为了逻辑完整好理解else:root.left=None# 右数组同上if len(right_nums)>=1:right_child=self.constructMaximumBinaryTree(right_nums)root.right=right_childelse:root.right=Nonereturn root

运行结果

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 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]

递归法

# 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 and root2!=None:return root2if root1!=None and root2==None:return root1if root1==None and root2==None:return None# 递归逻辑# 这里开辟一个新二叉树，不过也可以直接在tree1或者tree2上直接进行修改root_val=root1.val+root2.valroot=TreeNode(root_val)root.left=self.mergeTrees(root1.left,root2.left)root.right=self.mergeTrees(root1.right,root2.right)return root

给定二叉搜索树（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
输出：[]

递归法

# 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 root==val:return root# 递归终止条件if root==None:return Noneif root.val==val:return root# 递归逻辑 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 root.val>val:root=root.leftelif root.val<val:root=root.rightelse:# 相等情况return root# 没找到，返回Nonereturn None

运行结果

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

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

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

示例 1：

输入：root = [2,1,3]
输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

递归法

# 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.pre=Nonedef isValidBST(self, root: Optional[TreeNode]) -> bool:# 由于二叉搜索树按中序遍历就是单调递增，所以递归按照中序遍历来# 递归终止条件if root==None:return True# 递归逻辑left=self.isValidBST(root.left)if self.pre and self.pre.val>=root.val:return Falseelse:self.pre=rootright=self.isValidBST(root.right)return left and right

运行结果

有问题欢迎评论或私信