Category: Data Structure and Algorithms

树结构是数据结构中常常出现的，且用到非常多的一种数据结构。树结构中常见的有二叉树，二叉搜索树，AVL树以及B树等。树结构一般可以用递归去求解，如二叉树的遍历算法中，有先序，中序和后续遍历，一般的树结构的遍历中，有DFS（深度优先遍历）和BFS（宽度优先遍历）等都是用递归来实现。今天的实例中，有用递归直接实现的，也有用递归间接实现的。具体问题要具体分析，下面将要介绍几种具体的方法。 实例1：判断一颗二叉树是否是一个有效的二叉搜索树？ 浅析：根据二叉搜索树的递归定义，其每个节点的左子树都要比当前节点小，其右子树都要比当前节点大。一个直观的想法是：1、首先判断根节点是否满足要求，如果不满足，直接返回false，程序停止；2、再递归判断左子树是否满足要求，如果不满足，则程序返回false，依次退栈退出计算；3、再递归判断右子树是否满足要求，如果不满足，则程序返回false，依次退栈退出计算。但仔细分析发现这个思路有缺陷，不能保证右子树的最小节点比根节点要大，或者左子树的最大节点比根节点要小。这道题可以先用中序遍历（可以用递归）的方式将结果存起来，因为二叉搜索树的中序遍历结果是有序的。通过检查中序遍历结果的有序性即可判断是否为二叉搜索树。 实例2：二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。 浅析：首先判断当前节点的值，如果比low要小，说明左子树都要比low小，直接递归调用右子树即可。反之如果比high值要大，则递归调用左子树。如果在low和hight之间（假设其值为val），则，左子树上，递归调用trim[low,val]或trim[low,high],右子树上递归调用trim[low,high],或trim[val, high]。 实例3：给定二叉树的根节点root ，返回所有左叶子之和。 浅析：比较容易判断是否为叶子节点，当为叶子节点时，还需要考虑其父节点指向的左孩子是否为当前的叶子节点。递归实现的示例代码如下： 实例4：给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。 浅析：通过递归可以找到要删除的节点，如果节点是叶子节点，则好办。如果不是叶子节点呢，这个时候需要找到该节点的后继节点（successor）进行替换，然后递归调用后继节点的删除操作。由于后继节点一般是右子树的最左边的节点（可能是叶子节点，可能是含有右子树的节点），删除相对比较容易，不会再次出现递归调用。这道题的具体分析可以参考引文中的说明，比较详细。 后续将继续分析更多的树类型的数据结构的不同的问题场景和解题思路。 Reference

动态规划(dynamic programming)是数据结构与算法中常用到的策略算法，一般是通过状态转移方程和初始状态来一起定义问题，从而将更大的问题转换为前面已经计算出结果的动态的更新的过程。动态规划的难点在于状态转移方程的定义，有得问题比较显而易见，而有的问题可能就比较难以定义，需要多从实际问题中总结相关的经验。 今天向大家介绍动态规划的三个示例，具体一一向大家进行介绍。 实例1：爬楼梯问题，也是经典的动态规划问题，描述如下：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 分析及解答，假设爬到n阶有methods[n]种方法，则有两种可能，先爬到n-2阶，然后跨2个台阶到达n阶，或者先爬到n-1阶，然后跨1个台阶达到n阶。因此状态转移方程为：dp[n]=dp[n-1]+dp[n-2]。初始状态为dp[0]=0,dp[1]=1,dp[2]=2。然后就可以用递推来进行循环计算了。 实例2：找零钱问题，给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。 分析及解答：假设所需最少的硬币个数为f[amount]，则状态转移方程可以表示为f[amount]=min(f[amount-conins[j]+1)，其中要求满足amount-conins[j]>0的所有的j。在递推求解的过程中，可以用双重循环来实现，外层从1到amount，内层j从0到硬币的个数-1，然后循环有个条件，及当前amount-coins[j]要大于零。 实例3：给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。假设每一种面额的硬币有无限个。 分析和解答：这是和第二个问题相似但思路差别较大的问题，这里不做详细分析，直接先给出状态转移方程并作出一定的解释。状态转移方程为：problem(k,i) = problem(k-1, i) + problem(k, i-k)。其中problem(k,i) 为一个二维的状态，其中第一个维度表示用到了前面的k个硬币，i表示当前的凑的金额。problem(k-1, i)表示只用到了前面k-1个硬币就已经凑到了i，不需要第k个硬币，problem(k, i-k)表示用到了前面k个硬币凑到了i-k，已经用到了第k个硬币。 关于代码实现，后续有机会再向大家进行分享，也希望自己后面有机会向大家逐步整理关于数据结构和算法的较为系统全面的介绍，欢迎大家提出意见和建议。

动态规划是编程算法里边经常会用到的一种解决问题的思路，这里向大家介绍两个相对比较简单的示例。 示例1：一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？ 示例2：给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。 其中，第1题中可以将路径数目用二维数组path[m-1][n-1]来表示，path[i][j]就表示为从[0][0]位置起始开始走到[i][j]位置可能的路径。具体的实现方法和代码注释请参考链接。data-structures-algorithms/dp/unique-paths.cpp at main · kindlytree/data-structures-algorithms (github.com) 第2题，假设需要拼接的字符串的长度为s，则可以用一个can_concat[s+1]的数组来标记每一个从开始到index的位置是否可以有字典的单词标记出来。具体代码可以参考链接：data-structures-algorithms/dp/word-break.cpp at main · kindlytree/data-structures-algorithms (github.com)

上次分享过回溯问题的示例数独问题求解，今天向大家介绍一个类似的问题，n皇后问题，问题的来源是国际象棋中的皇后的摆法，两个皇后不能直面水平，垂直，对角线，否则不满足皇后摆放的要求。 这里也采用回溯的思路，假设为8皇后问题，从第一行开始摆放，用变量记录当前摆放行的candidate位置（记为valid_pos_），并且记录从第一行到当前行摆放的位置记录（path，path[i]即为第i行摆放的皇后的位置值）。我们的第一个函数即为根据已经摆放的path（前面已经摆放的行）去获取当前行的candidates，实现逻辑即为针对每一个前面的行的位置，计算其在当前行不可行的位置（竖直，对角线的位置），具体的代码如下。 其中正式的递归回溯过程的示例代码如下： 最后完整串起来的代码为： 完整的代码请参考链接： data-structures-algorithms/backtracking/n-queens.cpp at main · kindlytree/data-structures-algorithms (github.com)

在数据结构这门课程中，树结构是最重要的数据结构之一，有比较多的相关算法，比较有名的有：1、树的递归和非递归遍历；2、二叉搜索树的搜索过程；3、AVL树的构建过程；4、树的深度遍历（DFS）和宽度遍历（BFS）算法；5、其他更多的基于树结构的算法。树结构是图结构的基础，在实际应用中也有很多的问题基于树数据结构去建模。更多树结构的相关算法可以参考本文最后的链接，后面有机会也会进一步补充更多的相关算法。 今天要介绍的是一个树结构的一个中等难度左右的算法，即check一颗二叉树从根节点出发到叶子节点的路径上所有节点的和是否等于一个预先设定的值。 在这里介绍两种思路：1、通过递归遍历树结构找到所有的从根节点到叶子节点的路径，这些路径作为候选，一条一条路径check是否满足条件，如果满足可以将路径打印出来；2、通过递归程序直接判断是否存在这样的路径，这种条件下只返回true或false，不能打印出满足条件的路径。 下面主要介绍第一种算法思路（第二种代码思路请参考本文最后的链接），其主要代码如下所示，这里需要特殊说明的是c++中参数的传递技巧，如下面的代码中，path是普通变量，而all_paths是引用变量。普通变量在每一函数调用时会通过拷贝重新生成一个对象，而引用变量在所有递归调用过程中指向同一个数据变量。 两个算法完整的代码请参考链接： data-structures-algorithms/trees/path-sum.cpp at main · kindlytree/data-structures-algorithms (github.com)

回溯（backtracking）是遍历整个求解空间的一种常见的方式，一些有名的小游戏如数独的解法，八皇后游戏等都可以通过回溯的方法去求解。回溯的思想基本是通过递归进行的实现。这里以一个数独的场景为例向大家介绍一下实现的思路。 首先对数独的尚未填上数字的格子依次从左到右，从上到下的顺序进行填数字尝试，每填写当前的格子，可以按照条件首先筛选出可能的数字，并尝试将这些数字依次进行尝试填到格子里，当可以填写一个候选时，就跳到下一个还未填写数字的格子。如果后来发现下一个未填写的格子没有解（填写数字不能满足数独条件），则尝试下一个候选，如果所有候选都尝试后整个过程还是无解，则返回上一个格子的下一个候选再进行类似的尝试过程。 回溯过程也可以将看成时一个树的搜索过程，比如在数独场景，第一层节点可以看成是第一个格子的所有候选数字节点，回溯的过程是一个动态扩展这棵树的深度优先遍历的过程。如下示例代码显示了其过程，通过递归进行的实现，如果当前填写满足条件则继续下一个格子的填写，如果不满足则当前格子不填（撤回填写的数字）并考虑下一个候选，如果所有的候选都不满足，则退回到上一层搜索的状态继续搜索树的动态构建。 完整示例代码可以参考如下链接。data-structures-algorithms/backtracking at main · kindlytree/data-structures-algorithms (github.com)