94-99 好久没来打卡啦 ， 对不起。 我真的讨厌二叉树
我发现力扣 B站这种登录的电脑多了 之前的就会被挤掉 好麻烦0.0
94：中序遍历
不多讲了 递归真好写
# 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 inorderTraversal(self, root: TreeNode) -> List[int]: rel = [] def mintra(node): if node!= None: if node.left != None: mintra(node.left) rel.append(node.val) if node.right!= None: mintra(node.right) mintra(root) return rel 作者：yizhu-jia 链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/di-gui-zhen-hao-xie-wo-du-bu-xiang-xie-f-5mb5/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
95
：不同的二叉搜索树 2
本以为需要返回列表 得题解才知，需要的是返回一颗大树 可叹可叹
# 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 generateTrees(self, n: int) -> List[TreeNode]: def generateTrees(start, end): if start > end: return [None] alltree = [] for i in range(start,end+1): lefttree = generateTrees(start,i-1) righttree = generateTrees(i+1,end) for ltree in lefttree: for rtree in righttree: curtree = TreeNode(i) curtree.left = ltree curtree.right = rtree alltree.append(curtree) return alltree return generateTrees(1, n) if n else [] 作者：yizhu-jia 链接：https://leetcode-cn.com/problems/unique-binary-search-trees-ii/solution/ben-yi-wei-xu-yao-fan-hui-lie-biao-de-ti-xnht/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
96 不同的二叉搜索树 力扣把2放前面放上瘾了
第一次递归竟然超时了，，，
痛定思痛，想了想，可以把长度为n的位数都记录下来啊
但是还想着写成递归的形式
再想想 递归 递个P
两个循环搞定
要注意的是 i表示的是二叉树有多少个结点 所以从1开始 到n结束
j表示的是左结点有几个结点 从1开始 i结束 范围是0到i-1
class Solution: def numTrees(self, n: int) -> int: num_count = [1,1] for i in range(2,n+1): curcount = 0 for j in range(1,i+1): curcount += num_count[j-1]*num_count[i-j] num_count.append(curcount) return num_count[n] 作者：yizhu-jia 链接：https://leetcode-cn.com/problems/unique-binary-search-trees/solution/mo-mo-mo-mo-mo-mo-shu-zu-ji-lu-jie-guo-y-qypd/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
97 交错字符串
第一反应回溯 但是超时了 看答案是dp 结果写对了
思路就是看S1 的前I个和S2的前j个能不能表示 s3的前i+j个
注意的是 True的传播要分为从上面来还是从左边来
我行数表示s2的长度 列数是s1的长度
从左边来 说明要加入s1的元素 就比较s1那一位
从上面来 说明要加入s2的元素 就比较s2那一位
class Solution: def isInterleave(self, s1: str, s2: str, s3: str) -> bool: #超时的回溯 # n1 = len(s1) # n2 = len(s2) # n3 = len(s3) # if n3 != n1+ n2: # return False # def dfs(start1,start2,start3): # if start1 == n1 : # if s2[start2:] == s3[start3:]: # return True # else: # return False # if start2 == n2 : # if s1[start1:] == s3[start3:]: # return True # else: # return False # if s1[start1] == s3[start3] or s2[start2] == s3[start3]: # flag1 = False # flag2 = False # if s1[start1] == s3[start3] : # flag1 = dfs(start1+1,start2,start3+1) # if s2[start2] == s3[start3]: # flag2 = dfs(start1,start2+1,start3+1) # return (flag2 or flag1) # else: # return False # return dfs(0,0,0) n1 = len(s1) n2 = len(s2) n3 = len(s3) if n3 != n1+ n2: return False dp = [[False] * (n1+1) for j in range(n2+1)] dp[0][0] = True for col in range(1,n1+1): if dp[0][col-1] == True and s1[col-1] == s3[col-1]: dp[0][col] = True else: break for row in range(1,n2+1): if dp[row-1][0] == True and s2[row-1] == s3[row-1]: dp[row][0] = True else: break for row in range(1,n2+1): for col in range(1,n1+1): if dp[row-1][col] == True and s2[row-1] == s3[row+col-1]: dp[row][col] = True if dp[row][col-1] == True and s1[col-1] == s3[row+col-1]: dp[row][col] = True return dp[n2][n1] 作者：yizhu-jia 链接：https://leetcode-cn.com/problems/interleaving-string/solution/di-yi-fan-ying-hui-su-dan-shi-chao-shi-l-qcc0/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
98 验证二叉搜索树
中序遍历 不多说了
# 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: TreeNode) -> bool: flag = True cur = -2**31-1 def midtran(node): nonlocal flag nonlocal cur if node.left: midtran(node.left) if flag: if node.val <= cur: flag = False return False cur = node.val if node.right: midtran(node.right) midtran(root) return flag 作者：yizhu-jia 链接：https://leetcode-cn.com/problems/validate-binary-search-tree/solution/di-gui-de-zhong-xu-bian-li-by-yizhu-jia-2wf8/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
99：恢复二叉搜索树
我跟答案不一样啊
中序遍历
找到第一个比后面结点大的结点 就是交换的前一个结点 称为WRONGNODE
找到最后一个比WRONGNODE小的结点 交换他们。
# 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 recoverTree(self, root: Optional[TreeNode]) -> None: """ Do not return anything, modify root in-place instead. """ tempnode = TreeNode(val=-2**31-1) flag = True wrongnode = None def midtran(node): nonlocal flag nonlocal tempnode nonlocal wrongnode if node.left: midtran(node.left) if flag: if node.val < tempnode.val: flag = False wrongnode = tempnode return else: tempnode = node if node.right: midtran(node.right) def midtran2(node): nonlocal flag nonlocal tempnode nonlocal wrongnode if node.left: midtran2(node.left) if node.val < wrongnode.val: tempnode = node if node.right: midtran2(node.right) midtran(root) midtran2(root) tempnode.val,wrongnode.val = wrongnode.val,tempnode.val 作者：yizhu-jia 链接：https://leetcode-cn.com/problems/recover-binary-search-tree/solution/ahhahaha-zhe-ye-xing-xie-de-luan-qi-ba-z-3tws/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。