算法是如今面试比较重要的一部分，算法上的短板让人很头疼。坚持刷了一段时间关于二叉树的算法，写一些关于算法的个人思考。如很多大佬讲的二叉树很容易培养起架构思维，很庆幸从二叉树这种数据结构开始刷起。二叉树遍历主要迭代和递归为主，魅力在于理解并将核心处理逻辑处理成通用逻辑然后不断迭代或递归直到得到最终结果。

关于算法模板思考

开始接触算法时看到一些大佬的总结，搞出来各种模板。自认为这种方式是不可取的。个人认为算法的关键在于思维，在思维模式上可以有一定的步骤、逻辑，但是在解题时不能套用各种各样的模板。

首先会禁锢思维，解算法重要在于活跃的思维，模板也仅仅是某一种思维模式的具体代码实现，套不得。

其次因为模板仅仅反映了一种思维模式，一旦该模板不是最佳的读者套用了之后就很难在其他方面进行深入的思考，不能因小失大。

另外可能回增加负担，很简单的例子如为了记住A创造了B，如果B是很简单的东西还好，如果不是就糟糕了，会给自己大量的负担。套用模板本身能提高解决问题的速度，解决问题的方式是好的，但不要千篇一律。只有适合自己的方式才是最好的。

最后大家都要相信任何事物都是动态变化的、解决问题的方式可以有很多种，不要被所谓的模板套住。另外希望各位喜欢算法的同学，都要明确自己的目的，这是个枯燥漫长的过程必须给自己一个目的（激励不够就给个更大的）。祝诸各位顺利，本文我会分享出我的方法仅供大家参考，希望能有帮助，有不对的地方大家一起探讨。

抓住关键因子

首先要了解到什么是关键因子，了解任何一个事物时在基于他和其他事物共性的基础上要了解他的核心的特征、特殊行为等比较特殊关键的点，这些点就可以理解为关键因子。在同一事物上，对于关键因子的把握都是因人而异的，这也是这个世界的多样性的体现，在算法的世界里也是如此。抓住关键因子很重要，它是基础，不各种关键因子的组合到最后可能就变成了答案。下面以树这种数据结构为例说明。
树的关键因子是什么？根节点（一个），叶子节点（多个）。遍历是所有数据结构的共同的关键因子，那么树的迭代有什么特殊的呢？那么就是深度优先遍历（DFS）,广度优先遍历（BFS）了，很庆幸这些都有前人总结过可以拿过来直接理解了成为我们自己对于树的认知了。数据结构上遍历实现的关键因子是迭代法和递归法。树结构有什么不同吗？没有什么例外，每种数据结构的遍历都有自己的特殊点，而树DFS遍历分：前序、中序、后序。而BFS就没什么特殊。
ok，了解了树的关键因子后就可以进到二叉树里面。它最关键的因素在哪里？根节点，只有2个。
二叉搜索树又有什么不一样的呢？节点元素值，从左子节点值、根节点值、右子节点值，依次递增。
满二叉树？从上到下都是满的，所有节点都有两个子节点最后一层除外。
完全二叉树？除了最后一层的节点外上层的节点都是满的，且最后一层节点都是向左靠拢的。
当然还有其他的关键因子，并且从不同的维度衡量有不同的关键因子。如果要解答二叉树系相关的问题如上的关键因子是最关键的，要牢记于心的。如果在处理一些算法问题时题目中描述的事物的一些关键因子都不清楚就没有必要继续下去了，先完全搞懂了关键因子再说。

关于二叉树问题思维模式

二叉树的问题确实非常锻炼思维。强烈建议作为刚开始刷算法的同学作为开端。 下面直接给出个人常用的思维模式。
1.解读题目关键因子
2.读懂题目之后首先要想第一个问题：题目描述的答案诞生在哪里？可能第一个出现的答案比较广，没关系继续剖析，最后尽可能的明确范围。
3.思考答案的构造、收集？确定了答案诞生的位置后，判断答案的构建依赖什么状态。如果有依赖的状态那么下面就要思考如何获取依赖的状态可能要重复以上步骤。
4.思考如何遍历？明确了范围和答案的构造之后要思考如何遍历（一般涉及到数据结构都是要进行遍历的）下面给出几个选项，BFS/DFS，方向上：上下方向：自上向下、自下向上/左右方向：由左到右、由右到左。
5.思考问题的转化。不管前面的步骤没有出结果就要考虑能不能转化，当前问题是否选择直接解答，是否需要转化问题，要衡量利弊。（问题的转化可能持续在整个思考过程）

在一种思维模式下不同的选择会有不同的答案，当然思维模式也没有一层不变的。我把个人版的思考方式写出来，促进个人思考也供大家参考，在实战中不断的改进优化。下面我们通过一些二叉树的例子进行验证，实战。

二叉树的路径和问题

问题一

先从简单的开始，路径总和：就是判断树的路径中路径总和有没有等于目标值的。
按照我们的思维模式思考：
思考—：
1.关键因子
2.最初答案诞生在叶子节点
3.答案以返回值的形式逐层返回，只要子节点有一个满足条件即可。答案的判断依赖从上层节点传递下来的目标值。
4.dfs自上向下遍历。那么代码就可以很快写出来。
5.问题转化。转化成什么？可以转化成子节点是否满足路径和。

public boolean hasPathSum(TreeNode root, int targetSum) {
    if(root == null)return false;
    if(root.left == null && root.right == null && root.val == targetSum)return true;
    return hasPathSum(root.left,targetSum-root.val) || hasPathSum(root.right,targetSum-root.val);
}

思考二：
1.关键因子-->2.答案诞生在叶子节点（诞生之后就没必要继续循环了）-->3.答案诞生的判断依赖于已遍历路径的和-->4.DFS自上向下。5-->直接解答

boolean rs = false;
public boolean hasPathSum(TreeNode root, int targetSum) {
    dfs(root,targetSum,0);
    return rs;
}
public void dfs(TreeNode root, int targetSum, int currentSum) {
    if(root == null || rs)return;
    if(root.left == null && root.right == null  && currentSum+root.val == targetSum){
        rs = true;
        return;
    }
    currentSum += root.val;
    dfs(root.left,targetSum,currentSum);
    dfs(root.right,targetSum,currentSum);
}

当然不同的思考方式会有不同代码予以实现，当前仅仅以这两个思考结果为例来说明思维的模式。

问题二

路径总和III该题目在问题一的基础上多了几个关键因子，路径起点不要求是根子节点不要求是叶子节点但依然是自上向下的。另外要求的答案是达到要求路径的个数。
思考一：
1.关键因子：路径的方向--> 2.答案可能诞生在每个节点、每个节点可以是起点可以终点、每个节点可能是多条满足条件的路径。--> 3.构造答案需要什么？要拿到前面各个路径节点和列表，当前节点计算出满足条件的数量之和也参与每个节点的运算。-->4.自上向下 --->5.可以转化，选择直接处理
这种思维方式也能得到的结果是正面暴力破解的方案，时间复杂度和空间复杂度都较高。较复杂的点在于，构造答案这个步骤3，所以着重思考这一步，看能不能促成问题的转化。下面给出实现代码：

int count = 0;
public int pathSum(TreeNode root, int targetSum) {
    if (root == null) {
        return count;
    }
    pathSumHelper(root, new ArrayList<>(), targetSum);
    return count;
}

private void pathSumHelper(TreeNode root, List<Integer> choosed, int targetSum) {
    if (root == null) {
        return;
    }
    validChose(choosed, root.val, targetSum);
    pathSumHelper(root.left, choosed, targetSum);
    pathSumHelper(root.right, choosed, targetSum);

    cancelChose(choosed,root.val);

}

private void cancelChose(List<Integer> choosed, int val) {
    choosed.remove(choosed.size()-1);
    for (int i = 0; i < choosed.size(); i++) {
        int value = choosed.get(i) - val;
        choosed.set(i, value);
    }
}

private void validChose(List<Integer> choosed, int val, int targetSum) {
    for (int i = 0; i < choosed.size(); i++) {
        int value = choosed.get(i) + val;
        choosed.set(i, value);
        if (value == targetSum) {
            count++;
        }
    }
    if (val == targetSum) {
        count++;
    }
    choosed.add(val);
}

思考二：
1.接前置思考，如何转化？和转差，可以记录节点至根和的统计数据，如果存在和差值等于目标值，说明该节点之间的和是满足条件的。（被命名前缀和）--> 2.同上 --> 3.取统计数据中和=当前和-目标值 的数量，同时当前和记入统计数据中参与其他节点的运算--->4.自上向下。代码也可以很快写出来。

int count = 0;
Map<Integer,Integer> sumMap = new HashMap<>();
public int pathSum(TreeNode root, int targetSum) {
    sumMap.put(0,1);
    dfs(root,targetSum,0);
    return count;
}
public void dfs(TreeNode root, int targetSum,int currentSum){
    if(root == null)return;
    currentSum += root.val;
    count += sumMap.getOrDefault(currentSum - targetSum,0);
    sumMap.put(currentSum,sumMap.getOrDefault(currentSum,0)+1);
    dfs(root.left,targetSum,currentSum);
    dfs(root.right,targetSum,currentSum);
    sumMap.put(currentSum,sumMap.getOrDefault(currentSum,0)-1);
}

其中sumMap.put(0,1);兼容差值为0时的统计数据的记录。

如果没有问题的转化正面解答问题可能复杂度过高什么很难解决问题，这种转化也是有迹可循的，后面会探讨下。

问题三

二叉树最大路径和，这是一道困难题。求所有中的路径的最大和。
1.关键因子是路径的方向不限制从上到下。求最大的路径和。
2.答案可能诞生在任何两个节点之间。节点是不确定的，没办法直接确定。但是我们也没有必要确定是哪个节点，以单个节点来说最大和路径可能是两侧、可能是两侧合并起来的。那么问题转化成求包含两侧节点的最大值，拿到两侧最大值之后根据不同组合确定并记录路径和最大值。
3.有上面的分析，构造答案需要。两侧的最大和。可以通过方法直接返回。需要一个字段记录最大值。
4.自下向上遍历，在遍历的过程记录最大和。

int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
    dfs(root);
    return max;
}
public int dfs(TreeNode root){
    if(root == null)return 0;
    int leftMax = Math.max(dfs(root.left),0);
    int rightMax = Math.max(dfs(root.right),0);
    max = Math.max(max,root.val + leftMax + rightMax);
    return root.val + Math.max(leftMax,rightMax);
}

结语

本文主要想写一下对于算法个人的思考，当前仅以二叉树为例进行论述。后续会针对不同类型的问题进行剖析。是本人对于一些问题的思考做下记录，希望对一样对算法有兴趣的朋友有帮助。