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

目录

654.最大二叉树

思路

方法一： 递归基础版

方法二：递归使用下标

方法三：递归使用切片

心得收获 

617.合并二叉树

思路

递归法

迭代法

方法一： 递归 - 前序 - 修改root1

方法二：递归 - 前序 - 新建root

 方法三： 迭代

方法四：迭代优化 

700.二叉搜索树中的搜索 

思路

递归法

迭代法

方法一：递归

方法二：迭代

方法三：栈-遍历

心得收获

98.验证二叉搜索树 

思路

递归法

迭代法

方法一：利用中序递增性质，转换成数组

方法二：设定极小值，进行比较

方法三：直接取该树的最小值

方法四：迭代法

心得收获

654.最大二叉树

• 题目链接：力扣题目地址

• 文章讲解：代码随想录 

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

思路

最大二叉树的构建过程如下：

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

• 确定递归函数的参数和返回值

参数传入的是存放元素的数组，返回该数组构造的二叉树的头结点，返回类型是指向节点的指针。

• 确定终止条件

题目中说了输入的数组大小一定是大于等于1的，所以我们不用考虑小于1的情况，那么当递归遍历的时候，如果传入的数组大小为1，说明遍历到了叶子节点了。

那么应该定义一个新的节点，并把这个数组的数值赋给新的节点，然后返回这个节点。 这表示一个数组大小是1的时候，构造了一个新的节点，并返回。

• 确定单层递归的逻辑

这里有三步工作

1. 先要找到数组中最大的值和对应的下标， 最大的值构造根节点，下标用来下一步分割数组。
2. 最大值所在的下标左区间 构造左子树，这里要判断maxValueIndex > 0，因为要保证左区间至少有一个数值。
3. 最大值所在的下标右区间 构造右子树，判断maxValueIndex < (nums.size() - 1)，确保右区间至少有一个数值。

方法一： 递归基础版

class Solution:def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:if len(nums) == 1:return TreeNode(nums[0])node = TreeNode(0)# 找到数组中最大的值和对应的下标maxValue = 0maxValueIndex = 0for i in range(len(nums)):if nums[i] > maxValue:maxValue = nums[i]maxValueIndex = inode.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 NonemaxValueIndex = leftfor i in range(left + 1, right):if nums[i] > nums[maxValueIndex]:maxValueIndex = iroot = TreeNode(nums[maxValueIndex])root.left = self.traversal(nums, left, maxValueIndex)root.right = self.traversal(nums, maxValueIndex + 1, right)return rootdef 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 Nonemax_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

心得收获 

注意类似用数组构造二叉树的题目，每次分隔尽量不要定义新的数组，而是通过下标索引直接在原数组上操作，这样可以节约时间和空间上的开销。

一些同学也会疑惑，什么时候递归函数前面加if，什么时候不加if，这个问题我在最后也给出了解释。

其实就是不同代码风格的实现，一般情况来说：如果让空节点（空指针）进入递归，就不加if，如果不让空节点进入递归，就加if限制一下， 终止条件也会相应的调整。

617.合并二叉树

• 题目链接：力扣题目链接

• 文章讲解：代码随想录 

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

思路

递归法

那么我们来按照递归三部曲来解决：

1.确定递归函数的参数和返回值：

首先要合入两个二叉树，那么参数至少是要传入两个二叉树的根节点，返回值就是合并之后二叉树的根节点。

2.确定终止条件：

因为是传入了两个树，那么就有两个树遍历的节点t1 和 t2，如果t1 == NULL 了，两个树合并就应该是 t2 了（如果t2也为NULL也无所谓，合并之后就是NULL）。

反过来如果t2 == NULL，那么两个数合并就是t1（如果t1也为NULL也无所谓，合并之后就是NULL）。

3.确定单层递归的逻辑：

单层递归的逻辑就比较好写了，这里我们重复利用一下t1这个树，t1就是合并之后树的根节点（就是修改了原来树的结构）。

那么单层递归中，就要把两棵树的元素加到一起。

迭代法

使用迭代法，如何同时处理两棵树呢？

思路我们在二叉树：我对称么？ (opens new window)中的迭代法已经讲过一次了，求二叉树对称的时候就是把两个树的节点同时加入队列进行比较。

方法一： 递归 - 前序 - 修改root1

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

方法二：递归 - 前序 - 新建root

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

 方法三： 迭代

class Solution:def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:if not root1: return root2if not root2: return root1queue = 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.valif not node1.left and node2.left: node1.left = node2.leftif not node1.right and node2.right: node1.right = node2.rightreturn root1

方法四：迭代优化 

from collections import dequeclass Solution:def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:if not root1:return root2if not root2:return root1queue = deque()queue.append((root1, root2))while queue:node1, node2 = queue.popleft()node1.val += node2.valif node1.left and node2.left:queue.append((node1.left, node2.left))elif not node1.left:node1.left = node2.leftif node1.right and node2.right:queue.append((node1.right, node2.right))elif not node1.right:node1.right = node2.rightreturn root1

700.二叉搜索树中的搜索 

• 题目链接：力扣题目地址

• 文章讲解：代码随想录 

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

思路

递归法

1.确定递归函数的参数和返回值

递归函数的参数传入的就是根节点和要搜索的数值，返回的就是以这个搜索数值所在的节点。

2.确定终止条件

如果root为空，或者找到这个数值了，就返回root节点。

3.确定单层递归的逻辑

看看二叉搜索树的单层递归逻辑有何不同。

因为二叉搜索树的节点是有序的，所以可以有方向的去搜索。

如果root->val > val，搜索左子树，如果root->val < val，就搜索右子树，最后如果都没有搜索到，就返回NULL。

迭代法

一提到二叉树遍历的迭代法，可能立刻想起使用栈来模拟深度遍历，使用队列来模拟广度遍历。

对于二叉搜索树可就不一样了，因为二叉搜索树的特殊性，也就是节点的有序性，可以不使用辅助栈或者队列就可以写出迭代法。

对于一般二叉树，递归过程中还有回溯的过程，例如走一个左方向的分支走到头了，那么要调头，在走右分支。

而对于二叉搜索树，不需要回溯的过程，因为节点的有序性就帮我们确定了搜索的方向。

例如要搜索元素为3的节点，我们不需要搜索其他节点，也不需要做回溯，查找的路径已经规划好了。

方法一：递归

class Solution:def searchBST(self, root: TreeNode, val: int) -> TreeNode:# 为什么要有返回值: #   因为搜索到目标节点就要立即return，#   这样才是找到节点就返回（搜索某一条边），如果不加return，就是遍历整棵树了。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 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

方法三：栈-遍历

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 nodeif node.right:stack.append(node.right)if node.left:stack.append(node.left)return None

心得收获

本篇我们介绍了二叉搜索树的遍历方式，因为二叉搜索树的有序性，遍历的时候要比普通二叉树简单很多。

但是一些同学很容易忽略二叉搜索树的特性，所以写出遍历的代码就未必真的简单了。

所以针对二叉搜索树的题目，一样要利用其特性。

文中我依然给出递归和迭代两种方式，可以看出写法都非常简单，就是利用了二叉搜索树有序的特点。

98.验证二叉搜索树 

• 题目链接：力扣题目链接

• 文章讲解：代码随想录 

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

思路

要知道中序遍历下，输出的二叉搜索树节点的数值是有序序列。

有了这个特性，验证二叉搜索树，就相当于变成了判断一个序列是不是递增的了。

递归法

可以递归中序遍历将二叉搜索树转变成一个数组，然后只要比较一下，这个数组是否是有序的，注意二叉搜索树中不能有重复元素。

我们把二叉树转变为数组来判断，是最直观的，但其实不用转变成数组，可以在递归遍历的过程中直接判断是否有序。

这道题目比较容易陷入两个陷阱：

• 陷阱1

不能单纯的比较左节点小于中间节点，右节点大于中间节点就完事了。我们要比较的是 左子树所有节点小于中间节点，右子树所有节点大于中间节点。

• 陷阱2

样例中最小节点 可能是int的最小值，如果这样使用最小的int来比较也是不行的。

此时可以初始化比较元素为longlong的最小值。

递归三部曲：

• 确定递归函数，返回值以及参数

要定义一个longlong的全局变量，用来比较遍历的节点是否有序，因为后台测试数据中有int最小值，所以定义为longlong的类型，初始化为longlong最小值。

注意递归函数要有bool类型的返回值， 我们在二叉树：递归函数究竟什么时候需要返回值，什么时候不要返回值？ (opens new window)中讲了，只有寻找某一条边（或者一个节点）的时候，递归函数会有bool类型的返回值。

其实本题是同样的道理，我们在寻找一个不符合条件的节点，如果没有找到这个节点就遍历了整个树，如果找到不符合的节点了，立刻返回。

• 确定终止条件

如果是空节点 是不是二叉搜索树呢？

是的，二叉搜索树也可以为空！

• 确定单层递归的逻辑

中序遍历，一直更新maxVal，一旦发现maxVal >= root->val，就返回false，注意元素相同时候也要返回false。

迭代法

可以用迭代法模拟二叉树中序遍历，对前中后序迭代法生疏的同学可以看这两篇二叉树：听说递归能做的，栈也能做！，二叉树：前中后序迭代方式统一写法

方法一：利用中序递增性质，转换成数组

class Solution:def __init__(self):self.vec = []def traversal(self, root):if root is None:returnself.traversal(root.left)self.vec.append(root.val)  # 将二叉搜索树转换为有序数组self.traversal(root.right)def isValidBST(self, root):self.vec = []  # 清空数组self.traversal(root)for i in range(1, len(self.vec)):# 注意要小于等于，搜索树里不能有相同元素if self.vec[i] <= self.vec[i - 1]:return Falsereturn True

方法二：设定极小值，进行比较

class Solution:def __init__(self):self.maxVal = float('-inf')  # 因为后台测试数据中有int最小值def isValidBST(self, root):if root is None:return Trueleft = self.isValidBST(root.left)# 中序遍历，验证遍历的元素是不是从小到大if self.maxVal < root.val:self.maxVal = root.valelse:return Falseright = self.isValidBST(root.right)return left and right

方法三：直接取该树的最小值

class Solution:def __init__(self):self.pre = None  # 用来记录前一个节点def isValidBST(self, root):if root is None:return Trueleft = self.isValidBST(root.left)if self.pre is not None and self.pre.val >= root.val:return Falseself.pre = root  # 记录前一个节点right = self.isValidBST(root.right)return left and right

方法四：迭代法

class Solution:def isValidBST(self, root):stack = []cur = rootpre = 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 Falsepre = cur  # 保存前一个访问的结点cur = cur.right  # 右return True

心得收获

这道题目是一个简单题，但对于没接触过的同学还是有难度的。

所以初学者刚开始学习算法的时候，看到简单题目没有思路很正常，千万别怀疑自己智商，学习过程都是这样的，大家智商都差不多。

只要把基本类型的题目都做过，总结过之后，思路自然就开阔了，加油