作者Johngo

来源公众号Johngo学长

大家好，我是Johngo，再一次和大家聊聊校招。

昨天群里的一位粉丝私信我，说刚刚经历了今年不少公司的校招，由于某些特殊情况提前见了面试官。大概和我聊了聊。

私信和我说的大致内容是，刷题遗漏了关于「树」这部分数据结构的题目，开始感觉不好理解，后面就直接放弃了。

恰巧不巧，面试官跟他聊到了这部分。

不过，虽然这个答得不太好，其他还ok，所以还是拿到 Offer。

其实这位读者对我的印象还挺深刻的，前两个月记得和我巴拉巴拉说了不少，主要是今年会要经历秋招，有几个月了，准备的内容还挺多的，开始复习基础知识。再到今年暑假开始刷题，所以其实刷的题目还不是很多。

开始的时候准备了，基础的数据结构知识点的复习、计算机组成原理，计算机网络的八股文理解和记忆。都是必然要考察的内容。

再有就是 LeetCode 的题目和学校的项目，说起学校的项目真的不太推荐，这也是之前一直强调的，尽量提前实习，尽量多实习的原因。

多实习，可以把实习项目写进去，也是对接企业项目最直接的方式，自然被招进公司后也比较容易上手。

聊完，他给我说，感觉要来一场高考似的。

另外，目前最重要的一个项目，可能对于即将毕业的同学而言，比较陌生但是重要的，就是简历的制作。

有同学的简历一次搞定，而且这样的同学很多！一份简历打天下，后面几乎不改动了。其实我想说简历这个玩意儿真的还是需要不断的优化和整理的。

比如说：随着基础知识复习逐渐到位，对整理的项目的认识渐渐清晰。那简历一定也是要持续润色的。对面试官是可以输出更加清晰的基础知识和更加缜密的项目逻辑。

又有同学可能同时在找算法和大数据的工作。这种情况准备一份简历肯定是不行的。我要是 HR 看到大数据岗位的简历中有一半是算法的内容，大数据的项目寥寥无几，肯定是不过的。或者建议直接到算法组面试看看情况。

一份简历一定要方向垂直，垂直的内容占到90%。剩余的才是加分项。

再者，这段时间是各大公司的笔试、面试的高峰时段。所以建议大家做一个 Excel 表格来记录各个公司的笔试时间、面试时间，岗位描述、重点复习内容等等。又想起当年我校招的时候，乱的一批，最后才用一个 Excel 整理了出来，清晰了好多！

校招是从校园的生活（半社会环境）走向社会的一扇门，走出去是什么样子，大概校招能够决定一大半。所以，重视！！重视！！重视！！

不说其他的，坚持一下，拿出当年高考的心态，一举拿下一个又一个offer。高兴+高薪！

这位同学的面经后面会整理出来，给大家一个参考。

今天先聊聊他被问到的一个尴尬的内容，就是我一直强调的关于「树」这部分，它有一个很重要的思想：递归。

很多人没办法直接理解递归，也是咱们人脑很难去理解的一个逻辑处理。解释起来也很难，所以这几天不断有同学问到我。是一个难点也是一个重点。

像今天上午还有一个读者问到，我也在想怎么去更加详细的解释，也在想如何能把这个逻辑问题很清晰的展现出来。

「树」这部分最重要的是“递归”，其次就是分题型。

「自顶向下」题目，适合用递归和层次遍历的思想处理（深度和广度）；

「非自顶向下」题目，只适合用递归思想去处理（深度）；

以上就可以处理「树」这部分绝大多数的题目了。

话说回来，今天这位同学被聊到的是一个关于「二叉树路径」的问题，大概就是对标 LeetCode 中 113 题目。

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

记得之前的 112 题目，计算的是整个路径有没有路径和为 targetSum 的路径，同样是从根结点到叶子结点。

这个题目比较麻烦的一点是需要将满足要求的路径记录下来。

那么按照之前说的 DFS 和 BFS 来解决一下这个问题。

树结点定义

class TreeNode(object):
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

DFS深度遍历解决

二叉树的深度遍历中，由于在计算过程中需要保存当前计算时结点的信息（包括从根结点到当前结点的结点值之和以及从根结点到当前结点的路径list）。所以在进行递归遍历的时候，需要在这两方面做计算。

对 targetSum的处理：递归过程中，在遍历下一个结点的时候，将当前结点值减去，直到遍历到叶子结点的时候，判断不断被减去的 targetSum剩余值是否和叶子结点的值一致。如果一致，那么，记录该路径。如果不一致，放弃该路径。

看下图的一个说明

对路径的处理：递归过程中，不断记录路径，当遍历到叶子结点的时候，如果满足条件，则将该路径保存到最终的结果集中。

看代码：

def pathSum_dfs(self, root, targetSum):
    if not root:
        return
    res = []

    def dfs(root, target_sum, path, res_path):
        """
        :param root: 当前根结点
        :param target_sum: 当前目标值
        :param path: 当前路径列表
        :param res_path: 当前最终结果路径列表
        :return:
        """
        if not root:
            return
        if not root.left and not root.right and target_sum == root.val:
            res_path.append(path + [root.val])
        dfs(root.left, target_sum - root.val, path + [root.val], res_path)
        dfs(root.right, target_sum - root.val, path + [root.val], res_path)

    dfs(root, targetSum, [], res)
    return res

重点就是在tagetSum方面做了一些文章，仔细看看，其实就是一个先序遍历的过程。

BFS处理

BFS的处理思路是非常清晰的，详细可以看这篇文章：https://mp.weixin.qq.com/s/9U4P5zZIFppiJO_XK2QFDA

关于 BFS 处理树结构是非常清楚的。

思路就是在层序遍历过程中，遍历到各自结点的时候，记录当前信息。

如下：

图片来自（https://mp.weixin.qq.com/s/9U4P5zZIFppiJO_XK2QFDA）

很清晰的说明了在遍历到不同的结点的时候，记录：

当前结点

根结点到当前结点路径和

根结点到当前结点路径list

看本题代码：

def pathSum_bfs(self, root, targetSum):
    if not root:
        return
    res = collections.deque() # 保存最后结果list
    queue = collections.deque()
    queue.appendleft((root, root.val, [root.val])) # (结点,根到当前结点累加和,根到当前结点路径)

    while(queue):
        node, node_val, node_path = queue.pop()
        if not node.left and not node.right and node_val == targetSum:
            res.appendleft(node_path)
        if node.left:
            queue.appendleft((node.left, node_val+node.left.val, node_path+[node.left.val]))
        if node.right:
            queue.appendleft((node.right, node_val+node.right.val, node_path+[node.right.val]))
    return list(res)

Github

立马整理了关于「树」的典型例题，感兴趣的可查看：

https://github.com/xiaozhutec/PyCode

这几个月会逐步都整理出来，而且都以长图的形式进行展现，前后思路连贯，理解清晰。