整站优化网站报价,建设单位到江川区住房和城乡建设局网站,36氪wordpress,网站特效网这是基于代码随想录的每日打卡
654. 最大二叉树
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
创建一个根节点#xff0c;其值为 nums 中的最大值。递归地在最大值 左边 的 子数组前缀上 构建左子树。递归地在最大值 右边 的 子数组…这是基于代码随想录的每日打卡
654. 最大二叉树
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
创建一个根节点其值为 nums 中的最大值。递归地在最大值 左边 的 子数组前缀上 构建左子树。递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回 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, val0, leftNone, rightNone):
# 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_valmax(nums)rootTreeNode(max_val)# 最大值索引indexnums.index(max_val)# 左数组left_numsnums[:index]# 右数组right_numsnums[index1:]# 如果左数组个数大于1才能递归if len(left_nums)1:left_childself.constructMaximumBinaryTree(left_nums)root.leftleft_child# 如果左数组没有元素则指向空其实本来就默认指向空这里为了逻辑完整好理解else:root.leftNone# 右数组同上if len(right_nums)1:right_childself.constructMaximumBinaryTree(right_nums)root.rightright_childelse:root.rightNonereturn root运行结果 617. 合并二叉树
给你两棵二叉树 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, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) - Optional[TreeNode]:# 递归终止条件if root1None and root2!None:return root2if root1!None and root2None:return root1if root1None and root2None:return None# 递归逻辑# 这里开辟一个新二叉树不过也可以直接在tree1或者tree2上直接进行修改root_valroot1.valroot2.valrootTreeNode(root_val)root.leftself.mergeTrees(root1.left,root2.left)root.rightself.mergeTrees(root1.right,root2.right)return root700. 二叉搜索树中的搜索
给定二叉搜索树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, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def searchBST(self, root: Optional[TreeNode], val: int) - Optional[TreeNode]:if rootval:return root# 递归终止条件if rootNone:return Noneif root.valval:return root# 递归逻辑 if root.valval:return self.searchBST(root.left,val)if root.valval:return self.searchBST(root.right,val)运行结果 迭代法
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# 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.valval:rootroot.leftelif root.valval:rootroot.rightelse:# 相等情况return root# 没找到返回Nonereturn None运行结果 98. 验证二叉搜索树
给你一个二叉树的根节点 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, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def __init__(self):self.preNonedef isValidBST(self, root: Optional[TreeNode]) - bool:# 由于二叉搜索树按中序遍历就是单调递增所以递归按照中序遍历来# 递归终止条件if rootNone:return True# 递归逻辑leftself.isValidBST(root.left)if self.pre and self.pre.valroot.val:return Falseelse:self.prerootrightself.isValidBST(root.right)return left and right运行结果 有问题欢迎评论或私信
