前言

今天是算法训练营的第十七天（并非）？依旧是狂追之前漏写的总结，不过经过上一篇总结，我发现隔个几天再回顾貌似也有些许好处，但这种好处我觉得还是放在第二轮回顾时效果更佳明显，现在的任务是猛追债。

654.最大二叉树

题目链接：654. 最大二叉树

题目描述：

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

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

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

思路

首先分析一下题目要求，我们要做的事是确定nums中的最大值，以此创建根节点，然后以此为切割点，切割点左边的内容构建左子树，切割点右边的内容构建右子树。

下面是递归三部曲：

1.确定参数和返回值

参数主要是nums数组，返回值是返回构造完的根节点

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

2.确定终止条件

输入进的数组为空时，代表已经没有剩余需要处理的内容，此时就可以终止了

if not nums:
    return  

3.确定单步循环逻辑

这里我们每一步要做的是，找到数组中剩余的最大值，以此为切割点割成左右两部分，然后再分左右进行递归处理

maxVal = max(nums)
maxValIdx = nums.index(maxVal)
node =TreeNode(maxVal)
node.left = self.constructMaximumBinaryTree(nums[:maxValIdx])
node.right = self.constructMaximumBinaryTree(nums[maxValIdx + 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 not nums:
            return 
        maxVal = max(nums)
        maxValIdx = nums.index(maxVal)
        node =TreeNode(maxVal)
        node.left = self.constructMaximumBinaryTree(nums[:maxValIdx])
        node.right = self.constructMaximumBinaryTree(nums[maxValIdx + 1:])
        return node

617.合并二叉树

题目链接：617. 合并二叉树

题目描述：

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

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

返回合并后的二叉树。

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

思路

这道题我最初的做法是通过层序遍历来实现的，同时层序遍历两棵树并将两棵树相同位置的数值相加，最后输出就得到合并后的结果了。

层序遍历相对理解起来比较简单，下面讲一讲递归的实现思路。

递归也很好理解，实际要做的事情就是同步遍历两棵树，在相同位置的节点处将两棵树的节点数值相加得到合并后的结果。

然后是递归三部曲：

1.确定参数和返回值

参数是两棵树的根节点，返回最终合并后的根节点（实际上只要在其中一棵树上完成合并操作后返回该树即可，不用再构建一棵新树）

def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
    return root1

2.确定终止条件

这里的终止条件是两棵树中任意一棵为空就返回

if not root1:
    return root2
if not root2:
    return root1

3.确定单层递归逻辑

比较简单，就是把两个数相同位置的数值相加起来而已

root1.val += root2.val
root1.left = self.mergeTrees(root1.left, root2.left)
root1.right = self.mergeTrees(root1.right, root2.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 mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root1:
            return root2
        if not root2:
            return root1
        root1.val += root2.val
        root1.left = self.mergeTrees(root1.left, root2.left)
        root1.right = self.mergeTrees(root1.right, root2.right)
        return root1

700.二叉搜索树中的搜索

题目链接：700. 二叉搜索树中的搜索

题目描述：

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

思路

这道题相对来说比较简单，只是用来描述二叉搜索树的使用方法，总而言之就是大了取左边小了取右边，直到找到目标值。

实现写法：

# 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 not root:
            return root
        stack = [root]
        while stack:
            node = stack.pop()
            if node.val > val and node.left:
                stack.append(node.left)
            if node.val < val and node.right:
                stack.append(node.right)
            if node.val == val:
                return node
        return None

98.验证二叉搜索树

题目链接：98. 验证二叉搜索树

题目描述：

给你一个二叉树的根节点 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 = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        vec = []
        self.traversal(root, vec)
        for i in range(1, len(vec)):
            if vec[i] <= vec[i - 1]:
                return False
        return True

    def traversal(self, root, vec):
        if not root:
            return None
        self.traversal(root.left, vec)
        vec.append(root.val)
        self.traversal(root.right, vec)
        return vec

总结

今天的题目总体来说比较简单，通过以上训练，我们强化了对于二叉搜索树的使用理解，同时也进一步巩固针对二叉树的基础操作。