问题： (Problem:)

Given a binary tree and an integer k, return whether there exists a root-to-leaf path that sums up to k.

给定一个二叉树和一个整数k ，返回是否存在一个总和为k从根到叶的路径。

方法： (Approach:)

Since this is the first problem on this blog, let’s go step-by-step, and work through the solution. This problem is categorized as “easy”, and hence the solution shouldn’t be more than 10–20 lines of code.

由于这是此博客上的第一个问题，所以让我们逐步讲解并解决该解决方案。 此问题归类为“简单”，因此解决方案不应超过10-20行代码。

Like most binary tree problems, the best approach to the solution must start with thinking about left and right subtrees. For example, let take k=18 and the following binary tree:

像大多数二叉树问题一样，解决方案的最佳方法必须首先考虑左右子树。 例如，假设k=18和以下二进制树：

    8
   / \
  4   13
 / \   \
2   6   19

A path starting from root can only add up to 18, if any path starting from either left or right subtrees adds up to 18 - 8 = 10 — the problem is now reduced to a recursive problem looking at the left or right subtree. Going one level deeper, A path in the left subtree can add up to 10 if and only if any path in left sub-sub-trees adds up to 10 - 4 = 6. This in essence gives us the 10 line C++ solution to the problem.

如果从左子树或右子树开始的任何路径的总和为18-8 18 - 8 = 10 ，则从根开始的路径最多只能相加18现在，该问题已简化为查看左子树或右子树的递归问题。 要更深一层，在左子树的路径可以添加多达10当且仅当在左子子树的任何路径加起来10 - 4 = 6 。 本质上，这为我们提供了10行C ++解决该问题的方法。

First, let’s define our node structure with an integer val, and recursive left- and right- subtrees.

首先，让我们用整数val以及递归的左和右子树定义节点结构。

Next, let’s code our recursive solution for path-existence taking care of null subtrees.

接下来，让我们编写用于路径存在的递归解决方案，并照顾空子树。

There are basically two base cases:

基本上有两种基本情况：

1. When the root node itself is null, return false.
   当根节点本身为null时，返回false。
2. When the root node is a leaf (both left and right are null), simply compare the value of the root to the target.
   当根节点是叶子(左右均为空)时，只需将根的值与目标值进行比较即可。

The recursive case is simply subtracting the root’s value from target, and calling exists_path functions on left/right subtrees with the modified target.

递归的情况是简单地从目标中减去根的值，并在具有修改后的目标的左/右子树上调用exist_path函数。

测试： (Testing:)

Before we go further, I am coming to one of the most important parts of the coding interviews — the one most candidates ignore. Testing. Well-crafted unit tests makes your interview stand out, and might make a difference between a neutral and a strong-hire decision. I am going to use the Gunit testing framework for these blog posts.

在继续之前，我将介绍编码面试中最重要的部分之一-大多数候选人都忽略的部分。 测试。 精心设计的单元测试可以使您的面试脱颖而出，并可能在中立和强烈雇用的决定之间有所不同。 我将针对这些博客文章使用Gunit测试框架。

Some of the simplest and most obvious test cases are empty/single node trees. Here are 1-line tests for these cases:

一些最简单和最明显的测试用例是空/单节点树。 这是针对这些情况的一线测试：

A deeper binary tree needs a more elaborate construction. A builder pattern comes in quite handy here. Demonstrating a knowledge of patterns like this also makes your interview stand out. Here is how we can define a builder class for Node:

更深的二叉树需要更精细的构造。 构建器模式在这里非常方便。 展示这样的模式知识也会使您的访谈脱颖而出。 这是我们如何为Node定义构建器类的方法：

This allows us to construct the tree in the example above:

这使我们可以在上面的示例中构造树：

Here is how we can write a test using this pattern

这是我们可以使用这种模式编写测试的方法

最后但是同样重要的… (Last but not the Least…)

Most interviewers follow the initial question with a more advanced version. An advanced version of this question would be: Given a binary tree and an integer k, return a root-to-leaf path that sums up to k. You can use any data structure to return the path.

大多数面试官会以更高级的版本关注最初的问题。 这个问题的高级版本是：给定一棵二叉树和一个整数k ，返回从根到叶的路径，其总和为k 。 您可以使用任何数据结构来返回路径。

For the example above, an array with the values starting from the root, e.g. [8, 4, 6] would be an ideal return value.

对于上面的示例，具有从根开始的值(例如[8, 4, 6]的数组将是理想的返回值。

Always remember that the most advanced problems can be solved by slightly modifying the initial version of the algorithm. If you find yourself writing a new algorithm/code, stop and think! Can you use a standard container to store extra information? Can you cache part of the solution? Can you use an stl:: algorithm?

始终记住，可以通过稍微修改算法的初始版本来解决最高级的问题。 如果发现自己正在编写新的算法/代码，请停下来思考！ 您可以使用标准容器存储其他信息吗？ 您可以缓存部分解决方案吗？ 可以使用stl::算法吗？

For the modified problem above, one approach would be to use a std::unordered_map to store the successor relation in the desired path from root to leaf, and to update this map everytime a correct path is found.

对于上述修改后的问题，一种方法是使用std::unordered_map将后继关系存储在从根到叶的所需路径中，并在每次找到正确路径时更新此映射。

Here is the code:

这是代码：

This slightly modified exists_path implementation takes an additional pointer to std::unordered_map and modifies it in recursive call to keep track of the next node in the ideal path. The path itself can be constructed from the table:

这个经过稍微修改的exists_path实现需要一个pointer std::unordered_map的附加pointer ，并在递归调用中对其进行修改，以跟踪理想路径中的下一个节点。 路径本身可以从表中构造：

复杂 (Complexity)

Most interviews end with analyzing the computational complexity of the algorithm. For this problem, the complexity is simple. We visit every node of the tree once, and perform a constant amount of work for it. As a result, the complexity is O(N), where N is the number of nodes.

大多数采访以分析算法的计算复杂度结束。 对于这个问题，复杂度很简单。 我们访问树的每个节点一次，并为此执行恒定的工作量。 结果，复杂度为O(N) ，其中N是节点数。