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

654.最大二叉树

给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：

二叉树的根是数组中的最大元素。
左子树是通过数组中最大值左边部分构造出的最大二叉树。
右子树是通过数组中最大值右边部分构造出的最大二叉树。

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

示例：

654.最大二叉树

提示：

给定的数组的大小在 [1, 1000] 之间。

思路：

递归三部曲：

参数和返回值：数组可以在全局定义，不需要作为参数。参数是记录需要进行寻找最大值的数组区间的首尾两端下标即可。返回值应该是作为根节点的节点值。
终止条件：当首尾下标，left>right肯定是不正确的区间，说明区间不存在，直接返回None。如果left==right，说明区间只有一个数，直接将其作为节点返回。
递归逻辑：若是一个正常的区间，首先在这个区间中找到最大值下标，记录下来等着最后返回。由于当前处于区间[left,right]，所以该节点middle会将区间分为两个部分，即left到middle，middle到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 constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:

self.arr = nums

return self.getmaxtree(0, len(nums)-1)

def getmaxtree(self, left:int, right:int) -> Optional[TreeNode]: # 左闭右闭

if left > right:

return None

if left == right:

node = TreeNode(self.arr[left])

return node

maxval = self.arr[left]

middle = left

for i in range(left+1, right+1):

if self.arr[i] > maxval:

maxval = self.arr[i] # 这里记得要更新maxval值，debug才发现

middle = i

root = TreeNode(self.arr[middle])

root.left = self.getmaxtree(left, middle-1) # 注意是left，不是0

root.right = self.getmaxtree(middle+1, right) # 注意是right，不是len(self.arr)-1

return root

规范代码如下：

# 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 = rightclass Solution:

def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:

if len(nums) == 1:

return TreeNode(nums[0])

node = TreeNode(0)

# 找到数组中最大的值和对应的下标

maxValue = 0

maxValueIndex = 0

for i in range(len(nums)):

if nums[i] > maxValue:

maxValue = nums[i]

maxValueIndex = i

node.val = maxValue

# 最大值所在的下标左区间构造左子树

if 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

使用下标：

class Solution:

def traversal(self, nums: List[int], left: int, right: int) -> TreeNode:

if left >= right:

return None

maxValueIndex = left

for i in range(left + 1, right):

if nums[i] > nums[maxValueIndex]:

maxValueIndex = i

root = TreeNode(nums[maxValueIndex])

root.left = self.traversal(nums, left, maxValueIndex)

root.right = self.traversal(nums, maxValueIndex + 1, right)

return root

def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:

return self.traversal(nums, 0, len(nums))

使用切片：

class Solution:

def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:

if not nums:

return None

max_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

617.合并二叉树

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

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

示例 1:

617.合并二叉树

注意: 合并必须从两个树的根节点开始。

思路：

递归三部曲：

参数和返回值：两棵树的节点作为传入参数。返回一颗合并树，节点作为返回值。
终止条件：两个传入节点都为空。
递归逻辑：比较两个传入节点，如果一个为空，该节点值为另一个的值；否则为两个节点值之和，同时合并后的节点的孩子，是继续对两棵树对应位置的节点的递归调用得到的节点。需要考虑传入节点是否存在一个空值的情况，为了取得对应位置的节点，即本过程对应位置的左右孩子，若判断到其中一个节点为空值，为其赋值一个默认节点（属性为默认空值）。！！后来发现这部分考虑其实多余了，直接返回另外一个节点即可，因为返回另外一个节点，则其孩子也会被保留，而为空的节点本来就不存在孩子，对应位置的节点必然是非空节点的孩子。但以下我自己的实现由于不是直接返回非空节点，所以还是需要有这一部分的操作考虑。

代码实现如下：

# 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]:

return self.getnewnode(root1, root2)

def getnewnode(self, node1: Optional[TreeNode], node2: Optional[TreeNode]) -> Optional[TreeNode]:

if not node1 and not node2:

return None

node = TreeNode()

if node1:

node.val += node1.val

else:

node1 = TreeNode()

if node2:

node.val += node2.val

else:

node2 = TreeNode()

node.left = self.getnewnode(node1.left, node2.left)

node.right = self.getnewnode(node1.right, node2.right)

return node

规范代码：

# 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: TreeNode, root2: TreeNode) -> TreeNode:

# 递归终止条件:

# 但凡有一个节点为空, 就立刻返回另外一个. 如果另外一个也为None就直接返回None.

if not root1:

return root2

if 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 # ⚠️ 注意: 本题我们重复使用了题目给出的节点而不是创建新节点. 节省时间, 空间.

迭代：

class Solution:

def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:

if not root1:

return root2

if not root2:

return root1

queue = deque()

queue.append(root1)

queue.append(root2)

while queue:

node1 = queue.popleft()

node2 = queue.popleft()

# 更新queue

# 只有两个节点都有左节点时, 再往queue里面放.

if node1.left and node2.left:

queue.append(node1.left)

queue.append(node2.left)

# 只有两个节点都有右节点时, 再往queue里面放.

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.left

if not node1.right and node2.right:

node1.right = node2.right

return root1

700.二叉搜索树中的搜索

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

例如，

700.二叉搜索树中的搜索

在上述示例中，如果要找的值是 5，但因为没有节点值为 5，我们应该返回 NULL。

思路：

递归三部曲：

参数和返回值：参数为传入节点和搜索值。返回值为所找节点。
终止条件：找到了搜索值，返回该节点。遇到叶子节点且未找到搜索值，返回None。
递归逻辑：对当前节点的孩子继续调用递归，先对左孩子调用，如果存在返回值，则返回该值，否则继续对右孩子调用，如果存在则返回，不存在返回None。（忘记该题是二叉搜索树，应该判断节点大小和搜索值大小，如果搜索值小则搜索左孩子，否则搜索右孩子。自己实现的做法是任意二叉树）

代码实现如下：

# 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]:

return self.findnode(root, val)

def findnode(self, node: Optional[TreeNode], val: int) -> Optional[TreeNode]:

if not node:

return None

if node.val == val:

return node

if (des := self.findnode(node.left, val)) or (des := self.findnode(node.right, val)):

return des

else:

return None

规范代码：

class Solution:

def searchBST(self, root: TreeNode, val: int) -> TreeNode:

# 为什么要有返回值:

# 因为搜索到目标节点就要立即return，

# 这样才是找到节点就返回（搜索某一条边），如果不加return，就是遍历整棵树了。

if not root or 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)

迭代：

class Solution:

def searchBST(self, root: TreeNode, val: int) -> TreeNode:

while root:

if val < root.val: root = root.left

elif val > root.val: root = root.right

else: return root

return None

栈-遍历：

class Solution:

def searchBST(self, root: TreeNode, val: int) -> TreeNode:

stack = [root]

while stack:

node = stack.pop()

# 根据TreeNode的定义

# node携带有三类信息 node.left/node.right/node.val

# 找到val直接返回node 即是找到了该节点为根的子树

# 此处node.left/node.right/val的前后顺序可打乱

if node.val == val:

return node

if node.right:

stack.append(node.right)

if node.left:

stack.append(node.left)

return None

98.验证二叉搜索树

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

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

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

98.验证二叉搜索树

思路：

一开始没自己实现，思路不多，但能想到可能会有的坑：在判断的时候不能只判断左右孩子是否小（大）于节点值，还需要注意无论是左右孩子，都要满足该节点和该节点父亲的关系保持一致。（例如：左孩子的右孩子不能大于本节点）

根据文字解析提供的思路：一颗二叉搜索树的中序遍历应该是一个有序数组，所以对该二叉树进行中序遍历得到一个数组，如果是有序的则验证成功，否则验证失败。

递归三部曲：

参数和返回值：参数是传入节点。返回值是None
终止条件：节点为空。
递归逻辑：先对左孩子进行递归，然后对本节点进行操作（加入数组），然后对右孩子进行递归。

代码实现如下：

# 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:

if not root:

return True

self.arr = []

self.visit(root)

maxvalue = self.arr[0]

for i in range(1, len(self.arr)):

if self.arr[i] <= maxvalue:

return False

maxvalue = self.arr[i]

return True

def visit(self, node: Optional[TreeNode]) -> None:

if not node:

return

self.visit(node.left)

self.arr.append(node.val)

self.visit(node.right)

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

class Solution:

def __init__(self):

self.maxVal = float('-inf') # 因为后台测试数据中有int最小值

def isValidBST(self, root):

if root is None:

return True

left = self.isValidBST(root.left)

# 中序遍历，验证遍历的元素是不是从小到大

if self.maxVal < root.val:

self.maxVal = root.val

else:

return False

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 = rightclass Solution:

def __init__(self):

self.pre = None # 用来记录前一个节点

def isValidBST(self, root):

if root is None:

return True

left = self.isValidBST(root.left)

if self.pre is not None and self.pre.val >= root.val:

return False

self.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 = rightclass Solution:

def isValidBST(self, root):

stack = []

cur = root

pre = None # 记录前一个节点

while 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 False