求和为某个值。我们举个例子来分析一下。如下图所示，我们准备了一棵二叉树和一个整数22，经过观察，我们很容易看出它有两条路径的节点值之和分别为22、10、5、710，以及12以上两条路径都是从根节点开始到叶子节点的，也就是说路径总是从根节点开始的，所以我们首先需要遍历根节点。三种树遍历方法中，只有先序遍历先访问根节点。按照先序遍历的顺序访问这个二叉树。访问完节点10之后，再访问节点5。图中的二叉树没有指向父节点的指针。在访问节点5时，我们不知道之前经过了哪些节点。这时候我们需要准备一个栈来存放访问过的节点。当到达节点5时，路径包含两个节点：10、5。接下来，我们遍历到节点4，我们将这个节点压入栈中。此时我们已经到了叶子节点，但是栈中所有节点的总和为19，这个总和不等于输入的值22，所以与请求的路径不匹配。最后，我们要遍历的节点是12，在遍历这个节点之前，需要先回到节点10到节点5。还有，每次从子节点回到父节点，都需要删除子节点路径上的节点。最后，当节点10到达节点12时，路径上两个节点的值之和也是22，所以这也是一条满足要求的路径。分析到这里，我们发现了一些规律：当通过前序遍历访问到一个节点时，将该节点添加到路径中，累加该节点的值。如果节点是叶子节点，路径是如果节点值之和正好等于输入的整数，则当前路径满足要求。如果该节点不是叶节点，则继续访问其子节点。从节点路径栈中删除当前节点，递归上述过程，直到访问完二叉树的所有节点。实现代码有了清晰的思路之后，接下来我们就可以轻松编写代码了，如下：声明需要的变量：已经访问过的路径栈、符合预期的路径数组、取值之和当前访问过的节点从根节点开始，使用前序遍历访问所有节点，过滤并存储满足预期条件的路径findPath(root:Node,expectedSum:number):Array{if(root==null)返回[];//使用栈来存储访问过的路径constpathStack=newStack();//存储限定路径constpathList:Array=[];//当前访问路径的总和constcurrentSum=0;//从根节点开始搜索节点this.searchNode(root,expectedSum,pathStack,currentSum,pathList);返回路径列表；}取出根节点的值，累加，将根节点的值压入路径栈，判断是否访问过某个叶子节点。如果是叶子节点，且当前访问过的节点路径之和等于预期条件，则将路径栈中的路径放入符合条件的路径数组中。当前节点不是叶子节点，然后继续递归访问它的左、右子树，左子树、右子树都被访问了，说明当前路径不满足预期条件，将从中pop掉thepathstackprivatesearchNode(root:Node,expectedSum:number,pathStack:Stack,currentSum:number,pathList:Array){//累加当前访问节点的总和，将当前节点压入堆栈currentSum+=root.key;pathStack.push(root.key);//如果是叶子节点，且路径上节点值之和等于输入值，则将该节点存入当前路径栈constisLeaf=root.left==null&&root.right==null;如果（currentSum==expectedSum&&isLeaf）{pathList.push（pathStack.toString（））;}//非叶子节点，则遍历其子节点if(root.left!=null){this.searchNode(root.left,expectedSum,pathStack,currentSum,pathList);}if(root.right!=null){this.searchNode(root.right,expectedSum,pathStack,currentSum,pathList);}//当前节点不满足条件，出栈pathStack.pop();}测试用例接下来我们用文章开头的例子来测试上面的代码能否正确执行consttree:Node={key:10,left:{key:5,left:{key:4},右:{key:7}},右:{key:12}};consttargetVal=22;constresultPath=treeOperateTest.findPath(tree,targetVal);console.log(resultPath);如下图，两条路径计算成功。我们把节点12改成了20，然后再测试。结果如下，只有一条路径符合预期。示例代码本文使用的完整版代码请访问：TreeOperate.tsTreeOperate-test.ts
