代码随想录算法训练营第十八天（py）| 二叉树 | 654.最大二叉树、617.合并二叉树、700.二叉搜索树中的搜索、98.验证二叉搜索树

本文主要是介绍代码随想录算法训练营第十八天（py）| 二叉树 | 654.最大二叉树、617.合并二叉树、700.二叉搜索树中的搜索、98.验证二叉搜索树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

654.最大二叉树

力扣链接
给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：
二叉树的根是数组中的最大元素。
左子树是通过数组中最大值左边部分构造出的最大二叉树。
右子树是通过数组中最大值右边部分构造出的最大二叉树。
通过给定的数组构建最大二叉树，并且输出这个树的根节点。

思路

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

class Solution:def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:# 如果数组就剩一个元素，就是到叶子节点了# 定义一个新节点if len(nums)==1:return TreeNode(nums[0]) # 1.找到数组中最大的值和对应的下标， 用最大的值构造根节点node = TreeNode(0)maxval = 0maxvalidx = 0for i in range(len(nums)):if nums[i]>maxval:maxval = nums[i]maxvalidx = inode.val = maxval# 2.最大值左边的元素构建左子树if maxvalidx > 0:left_list = nums[:maxvalidx]node.left = self.constructMaximumBinaryTree(left_list)# 3.最大值右边的元素构建右子树if maxvalidx < len(nums)-1:right_list = nums[maxvalidx+1:]node.right = self.constructMaximumBinaryTree(right_list)return node

617.合并二叉树

力扣链接
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

思路递归-前序遍历

class Solution:def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:if root1 == None:return root2if root2 == None:return root1# 定义一个新树的根节点root = TreeNode(0)root.val = root1.val + root2.valroot.left = self.mergeTrees(root1.left, root2.left)root.right = self.mergeTrees(root1.right, root2.right)return root

700.二叉搜索树中的搜索

力扣链接
给定二叉搜索树（BST）的根节点和一个值。你需要在BST中找到节点值等于给定值的节点。返回以该节点为根的子树。如果节点不存在，则返回 NULL。
BST的特性为左边的比中间大，右边的比中间小，且BST的子树依旧是BST。

思路1 递归

class Solution:def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:if root == None or root.val == val:return root# val小，要找的值在左边if root.val > val:return self.searchBST(root.left,val)# val大，要找的值在右边        if root.val < val:return self.searchBST(root.right,val)

思路2 迭代

class 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.验证二叉搜索树

力扣链接
给定一个二叉树，判断其是否是一个有效的二叉搜索树。

思路中序遍历后判断是否有序

class Solution:def isValidBST(self, root: Optional[TreeNode]) -> bool:res = []def dfs(node):if node is None:returndfs(node.left)res.append(node.val)dfs(node.right)dfs(root)for i in range(1,len(res)):if res[i]<=res[i-1]:return Falsereturn True