Python小白 Leetcode刷题历程 No.96-No.100 不同的二叉搜索树、交错字符串、验证二叉搜索树、恢复二叉搜索树、相同的树

写在前面：

作为一个计算机院的大学生，总觉得仅仅在学校粗略的学习计算机专业课是不够的，尤其是假期大量的空档期，作为一个小白，实习也莫得路子，又不想白白耗费时间。于是选择了Leetcode这个平台来刷题库。编程我只学过基础的C语言，现在在自学Python，所以用Python3.8刷题库。现在我Python掌握的还不是很熟练，算法什么的也还没学，就先不考虑算法上的优化了，单纯以解题为目的，复杂程度什么的以后有时间再优化。计划顺序五个题写一篇日志，希望其他初学编程的人起到一些帮助，写算是对自己学习历程的一个见证了吧。

有一起刷LeetCode的可以关注我一下，我会一直发LeetCode题库Python3解法的，也可以一起探讨。

觉得有用的话可以点赞关注下哦，谢谢大家！
········································································································································································
题解框架：

    1.题目，难度
    2.题干,题目描述
    3.题解代码（Python3（不是Python，是Python3））
    4.或许有用的知识点（不一定有）
    5.解题思路
    6.优解代码及分析（当我发现有比我写的好很多的代码和思路我就会写在这里）

········································································································································································

No.96.不同的二叉搜索树

难度：中等
题目描述：

在这里插入图片描述

题解代码（Python3.8）

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0] * (n+1)
        dp[0] = 1
        dp[1] = 1
        
        for i in range(2,n+1):
            for j in range(i):
                dp[i] += dp[j] * dp[i-j-1]

        return dp[-1]

或许有用的知识点：
这道题要用到动态规划的方法。
这道题所求的数在数学上又叫做卡特兰数（Catalan number），具体介绍如下：

在这里插入图片描述
在这里插入图片描述

解题思路：
这道题是求解法总数的问题，我们可以使用动态规划的方法。套用动态规划算法的模板，对于这道题，令dp[n]为第n位的解法总数，则动态规划的三要素为：
状态：假设n为根节点，当i为根节点时，其左子树节点个数为[1,2,3,...,i-1]，右子树节点个数为[i+1,i+2,...n]，所以当i为根节点时，其左子树节点个数为i-1个，右子树节点为n-i，即f(i) = G(i-1)G(n-i)。
状态转移方程：dp[i]+=dp[j]dp[i-j-1]
边界条件：dp[0]=1,dp[1]=1。

No.97.交错字符串

难度：困难
题目描述：

在这里插入图片描述

题解代码（Python3.8）

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        l1 = len(s1)
        l2 = len(s2)
        l3 = len(s3)
        if l1 + l2 != l3:
            return False
        dp = [[False]*(l2+1) for _ in range(l1+1)]
        dp[0][0] = True         #首位置
        for j in range(1,l2+1):   #第一行
            dp[0][j] = dp[0][j-1] and s2[j-1] == s3[j-1]
        for i in range(1,l1+1):   #第一列
            dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1]

        for i in range(1,l1+1):
            for j in range(1,l2+1):
                dp[i][j] =(dp[i-1][j] and s1[i-1] == s3[i+j-1]) or (dp[i][j-1] and s2[j-1] == s3[i+j-1])
        
        return dp[-1][-1]

或许有用的知识点：
这道题要处理字符串，验证合法性，可以使用动态规划的方法，且有动态规划问题中‘自底向上’思路和‘自顶向下’思路区别的分析（‘自顶向下’的思路可能要用到‘缓存+递归’的方法，此时会用到functools.lru_cache装饰器，再本题’优解代码及分析中有详细介绍‘）。
‘自底向上’的思路是比较容易想到的，是先依次解决小问题，最终解决所求问题；在树形结构中，就是先解决底部的问题，再一层层解决向上的问题，最后解决顶部的所求问题。
而‘自顶向下’的思路是比较不容易想到的，是先看解决最终问题依次需要解决哪些小问题，再解决所有的小问题；在树形结构中，就是先看解决顶部的问题需要解决哪些子问题，再看解决这些子问题需要解决哪些子问题，直到解决最底部的问题。引用知乎大佬给出的生动形象的小例子：
某日小明上数学课，他的老师给了很多个不同的直角三角板让小明用尺子去量三角板的三个边，并将长度记录下来。两个小时过去，小明完成任务，把数据拿给老师。老师给他说，还有一个任务就是观察三条边之间的数量关系。又是两个小时，聪明的小明连蹦带跳走进了办公室，说：“老师，我找到了，三条边之中有两条，它们的平方和约等于另外一条的平方。”老师拍拍小明的头，“你今天学会了一个定理，勾股定理。它就是说直角三角形有两边平方和等于第三边的平方和”。
另一个故事，某日老师告诉小明“今天要教你一个定理，勾股定理。”小明说，“什么是勾股定理呢？”“勾股定理是说，直角三角形中有两条边的平方和等于第三边的平方。”然后老师给了一大堆直角三角板给小明，让他去验证。两个小时后，小明告诉老师定理是正确的.
两个故事刚好是语法分析里面对应的两个方法：第一个故事说的是自底向上的分析方法，第二个故事说的是自顶而下的分析方法。

解题思路：
这道题是处理字符串，验证合法性的问题，我们可以使用动态规划的方法。套用动态规划算法的模板，对于这道题，令dp[i][j]表示s1的前i个字符和s2的前j个字符是否能构成s3的前i+j个字符,则动态规划的三要素为：
状态：
第i行第j列的状态为：s1的前i-1个字符和s2的前j个字符能否构成s3的前i+j−1位，且s1的第i位（s1[i−1]）是否等于s3的第i+j位（s3[i+j−1]）,或者s1的前i个字符和s2的前j−1个字符能否构成s3的前i+j−1位，且s2的第j位（s2[j−1]）是否等于s3的第i+j位（s3[i+j−1]）。
状态转移方程：dp[i][j] =(dp[i-1][j] and s1[i-1] == s3[i+j-1]) or (dp[i][j-1] and s2[j-1] == s3[i+j-1])
边界条件：
dp[0][0] = True
for j in range(1,l2+1): dp[0][j] = dp[0][j-1] and s2[j-1] == s3[j-1]
for i in range(1,l1+1): dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1]

优解代码及分析：
优解代码（Python3.8）

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        l1 = len(s1)
        l2 = len(s2)
        l3 = len(s3)
        
        import functools
        @functools.lru_cache(None)
        def recursion(i,j,k):
            if i == l1 and j == l2 and k == l3:
                return True
            if k < l3:
                if i < l1 and s1[i] == s3[k] and recursion(i+1,j,k+1):
                    return True
                if j < l2 and s2[j] == s3[k] and recursion(i,j+1,k+1):
                    return True
            return False
        
        return recursion(0,0,0)

分析：
这其实是缓存+递归的方式，原理和动态规划一样。要用到functools.lru_cache装饰器。

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

No.98.验证二叉搜索树

难度：中等
题目描述：

在这里插入图片描述

题解代码（Python3.8）

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        res = []
        def recursion(root):
            if not root:
                return 
            recursion(root.left)
            res.append(root.val)
            recursion(root.right)
        recursion(root)
        return (res == sorted(res)) and (len(set(res)) == len(res))

或许有用的知识点：
这道题使用了递归的思想。

解题思路：
因为二叉搜索树中序遍历是递增的,所以我们可以中序遍历判断前一数是否小于后一个数。运用递归的方法，设置一个递归函数，将整个树从左到右输出，在判断是否递增。

No.99.恢复二叉搜索树

难度：困难
题目描述：

在这里插入图片描述
在这里插入图片描述

题解代码（Python3.8）

class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        self.firstNode = None
        self.secondNode = None
        self.preNode = TreeNode(float('-inf'))

        def recursion(root):
            if not root:
                return
            recursion(root.left)
            if (self.firstNode == None) and (self.preNode.val >= root.val):
                self.firstNode = self.preNode
            if self.firstNode and (self.preNode.val >= root.val):
                self.secondNode =root
            self.preNode = root
            recursion(root.right)
        
        recursion(root)
        self.firstNode.val,self.secondNode.val = self.secondNode.val,self.firstNode.val

或许有用的知识点：
这道题用了递归的思想。
这道题firstNode,secondNode,preNode三个变量在多个函数中被引用，可以在变量前加’self.’。
float("inf"), float("-inf")分别表示正负无穷。

解题思路：
这道题难点,是找到那两个交换了的节点,把它交换过来就行了。这里我们二叉树搜索树的中序遍历(中序遍历遍历元素是递增的)，如下图所示, 中序遍历顺序是 4,2,3,1,我们只要找到节点4和节点1交换顺序即可。这里我们有个规律发现这两个节点：第一个节点,是第一个按照中序遍历时候前一个节点大于后一个节点,我们选取前一个节点,这里指节点4;第二个节点,是在第一个节点找到之后, 后面出现前一个节点大于后一个节点,我们选择后一个节点,这里指节点1。

No.100.相同的树

难度：简单
题目描述：

在这里插入图片描述

题解代码（Python3.8）

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if (not p) and (not q):
            return True
        if (p and q) and (p.val == q.val):
            return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
        return False

或许有用的知识点：
这道题要用到递归的思想。

解题思路：
这道题运用递归的方法，设置一个递归函数，当p和q都空时return True；当p和q都非空时，如果p和q的值相等，return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)，判断p和q的左右子支的值是否相等。