这周Leetcode的7个题主要选了涵盖了DP，排序，回溯，双指针，树遍历和变换等，有稍微总结了一些方法和套路，同步到个人博客。都用Python自己实现了一下下，也看了一下下大神们的方法。

我自己写的第一遍能AC的代码，也都放上去了，大多数写的比较丑陋冗余。主要是为了对比看到和大神的方法之间存在什么差异，进而得到思维上的加成，然后自己理解再写了一遍加深印象，日后也可以多来回顾一下。

经典题，说实话写这个题花了不少时间，尤其是想清楚这个里外里的道理。这道题是一道典型的背包问题，但是在成为背包问题之前，要做一些必要的转换。

• 首先，题目要求2个子数组和相等，因此，只有大数组的和为偶数，才可能使得2个子数组和是相等，所以一旦和为奇数就可以立即排除输出False。
• 其次对于和为偶数的情况，可以将总和除2作为每个子数组的目标和，所以问题就转化为找出子数组和为$target = sum / 2$。
• DP问题就是要借助DP的思想，就要写一下状态转移方程，作为写代码的指导思想。动态规划都是借助一个2维或者1维的表格来建立整个过程，于是我们借一个例子来画一下表格：

行表示每一个数，列表示能够达到所有可能的和（这里可以记忆一下，DP问题是由繁化简，所以一定是有状态从最起始开始一直到我们的目标，在例子中起始为0，目标是11，中间所有可能的值也都要考虑，这点和背包问题是一样的）。由于我们现在的问题是数组和能否达到某个固定的数，因此可以写得递推公式为 $$dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]$$

稍微解释一下这个公式，第一项$dp[i-1][j]$是说，如果上一行（i-1）已经满足和为j了，那下一行也一定会满足和为j，所以i项不加也可以满足，状态照搬下来就可以，就好比01背包问题，不取当前项，最大价值仍然延续上一个状态一个意思。而$dp[i-1][j-nums[i]]$表示前i-1个数，在target - nums[i ]处已经满足，那加上nums[i]也同样会满足，显示了DP的递推性。这样主体就搭建好了。

在这里也要注意一下初始值的问题，j为0意味着和为0，也就是不取任何数，所以dp[:][j=0]要设置为True（一个都不取，什么都不用做就满足了，也是强）。于是就可以写下代码了：

这里有可以改进的地方，就是原始是采用了一个二维数组来存储数据的，其实可以优化为一维数组的，这一点和背包问题是一致的，需要注意的是内层的遍历要降序遍历，来防止对已经生成的数据做重复修改，不展开了，可以参考。改写如下：

这题有用别的奇技淫巧来解的，我就不推荐了，主要还是可以借机会复习01背包动态规划的思想，以及转移状态的确定和思维的转换。其他大神的办法无非是在DFS上做文章，我是真的想不到，就老老实实的吧，毕竟慢学。

这道题聊解题没有任何意义，主要是周末想借这个机会复习一下所有的排序算法思想，先给个最简单的题解吧。

这里顺便复习几个比较常用的排序算法：冒泡，选择，插入，归并，快排。 冒泡：

插入，这个还是想了一下的，主要是用while的话更加清楚一些。

这里面比较难想的是插入，归并和快排，有必要做一个专题来攻克一下。虽然以前也学过，而且说来说去也大概知道原理，但是真正自己实现的时候，还是没有那么快能解决。

一道经典的回溯题，看到这样的例子，第一反应就是用DFS搭配回溯，既然是深度优先遍历，一般会用一个visited来记录遍历到的位置，运用for加递归的方式进行遍历，设置退出的条件。回溯算法需要将visited的状态回退，这里运用了一个pop方法将栈中的元素末尾弹出后回溯到上一层状态。这里因为是for循环加上递归的结构，递归其实可以看成是一个一般的函数调用（有返回值），当次的for循环结束后，弹出末尾元素，下一次循环后再压入，以此往复。

AC了，看到另外的解法，避免了在循环中进行判断，而是在传入下层递归的时候，就只传入除去当次循环的那个元素后的剩余元素，要巧妙的多。

经典题，求回文子串个数，应该只要循环加递归就可以搞定了，理一下思路：回文的特征就是以某一个中心位置为轴对称，但是这里有一点要注意就是奇数个子串有中心位置，但是偶数个数的子串中心位置应该是两个数。明确了这一点之后，循环到某一个位置时，设置两个指针i和j分别从中心位置++和--，直到任何一个指针到达边界小于0或超过数组长度截止，如果有满足 s[i] == s[j] 就继续迭代进行。思路不难，实现了一下：

AC了，看了个大神的方法，用了for嵌套while的结构，看着还是挺清楚的，我承认我之前非要写个递归，其实就是想自己练练写递归，也没什么特别的道理哈哈。这里用了一个技巧来一步实现奇数偶数的判断，left = center / 2, right = center / 2 + center % 2. 实现如下：

最近翻看了很多树类的题目，凡是见到树的题目，脑子就要有一个递归的大体框架，如果递归比较弱的，比如我自己，就可以有针对性的练几个树的题目提高一下。 这一题，乍一看也挺简单的，直觉上利用BST树的基本性质，左小右大，于是写了一个遍历左子树的递归，但是报错，这才发现如果K值过大的话，还是需要右子树的，会觉得需要对K做分情况考虑了一下子好像觉得有点复杂了。而像这种第几个XXX的题目，排序似乎永远都是一个不错的方案，全局排序会导致较大的时间开销，设置条件提前停止是一个比较不错的优化方案。

由于每一棵树都是左>根>右，因此采用中序遍历（LDR）代码如下：

为了训练，也可以用非递归的形式来解，但是这边需要，我这里练习并记录一下

这里的两个方法，其实都只是直接考虑全局排序的，时间消耗是很大的，从AC后的耗时可以看出，要优化的话，就要从这个k入手，记录并精准返回第k个然后程序结束。写一下：

一道简单题，python可以导入math包，或者用x**(1/2)都可以得到结果，但是这不是目的。这是一题二分查找的题，考虑了一些边界条件和结束条件，就写了如下的一个方法，有点繁杂但是可以AC：

我是故意写递归的，目的是让自己习惯。下面照着大神的做法，理解了写了个别的方法

这里巧妙的在于，初始是0也就不需要额外判断了，然后把我上面的三个条件并成了一个，如果x在 mid * mid 和 (mid+1) *（mid+1）之间即输出。不过这个题，只要想到二分查找就至少答到题意了，有些优化可能第一时间想不到也没关系。就这样吧。

还可以进一步简化为这样子：

总体来说，树类的问题套路一般就是直上直下的遍历，采用递归或者while的循环都可以，遍历的3种模式中，前序遍历，中序遍历可以相互转化，后序遍历和层次遍历（BFS）可以一起记忆。另一类就是DFS，需要维护和记录一个visited数组。

大概就是这样吧，依旧慢学，下周继续。

使用create创建二叉树

通过 create 也可以得到同样的效果

以上是内存溢出为你收集整理的python之二叉树的建立全部内容，希望文章能够帮你解决python数据结构之二叉树的建立实例所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。

二叉树(Binary Tree)时数据结构中一个非常重要的结构，其具有。。。。(此处省略好多字)。。。。等的优良特点。

之前在刷LeetCode的时候把有关树的题目全部跳过了，(ORZ：我这种连数据结构都不会的人刷j8Leetcode啊！！！)

所以 ！！！敲黑板了！！！今天我就在B站看了数据结构中关于树的内容后，又用我浅薄的Python大法来实现一些树的建立和遍历。

关于树的建立我觉得层序建立对于使用者来说最为直观，输入很好写。(好吧，我是看LeetCode中的树输入都是采用层序输入觉得非常好)

这一段代码太好理解了好吧，就不BB了。

1 #建立二叉树是以层序遍历方式输入，节点不存在时以 'None' 表示

creatTree即为层序建立二叉树的函数，传入的参数为一个层序遍历的数组，就是将树节点从左往右，从上往下一次放入数组中，如果某个节点不存在则用None来表示。

第3-4行，判断根节点是否为空。 如果根节点都为空，那树(shuo)就(ge)不(j)存(8)在了，直接返回就好了。

第5行，将元素列表中的第一个元素取出新建根节点，最后返回的即为根节点

第6行，创建了一个Nodes列表中，用于存放树中的节点，每生成一个节点就将其放入该列表中，可以看成是一个队列(这么说好像也不是特别规范，因为后面只是取列表中的元素，没有弹出首元素)，此处将根节点存入。

第7行，创建变量j用于nodeList中元素的索引，初始为1.因为第0个元素已经创建根节点了。

第8行，依次取出Nodes列表中的节点，对其创建左子节点和右子节点

第9行，首先判断取出的Nodes是否为空，如果为空，说明此处没有节点，就无需创建子节点，否则进行子节点的创建

第10行，为该节点创建左节点，其值就是索引j的所对应的值，如果nodeLists[j] == None 说明没有该子节点，就不用创建了，即Child = None

第11行，将新建的节点加入Nodes数组，使其在for循环中可以继续为其添加子节点

第12行，j加1，这样刚好使每一个nodeList的元素对应一个节点了

第13行，判断j的值，如果与nodeList值相等说明全部节点已经添加完毕了，直接返回head根节点就完成了树的建立

第15-19行，为节点添加右节点，与添加左节点的逻辑是一样的，就不在赘述了

好了代码注释完毕，我们再通过结合实例来解释一下：

j溢出，则返回head根节点，结束二叉树的建立

PS：如果node为空节点的话，就会直接跳过空节点。

二叉树遍历(神用的递归)

#head为二叉树的根节点

#head为二叉树的根节点

#head为二叉树的根节点

对中序遍历，费了我九牛二虎之力画了一个程序执行的图，红色箭头代表程序执行的过程，依然以a = [1,2,3,4,5,None,6,None,None,7,8]为例

这个图看上去不是很清楚，右键保存到本地看会清楚很多的，我把每一步递归的树都画出来了，这样更加方便理解。

最后，致敬大佬，祝各位学有所成。

【转载表明出处，谢谢】