binary-tree - 在二叉树中打印具有给定总和的所有路径的算法

Question

以下是面试题。

You are given a binary tree (not necessarily BST) in which each node contains a value. Design an algorithm to print all paths which sum up to that value. Note that it can be any path in the tree - it does not have to start at the root.

虽然我能够找到树中从根开始的所有路径都具有给定的总和，但对于不是从根开始的路径，我无法这样做。

Answer 1

嗯，这是一棵树，不是图。所以，你可以做这样的事情:

伪代码:

global ResultList

function ProcessNode(CurrentNode, CurrentSum)
    CurrentSum+=CurrentNode->Value
    if (CurrentSum==SumYouAreLookingFor) AddNodeTo ResultList
    for all Children of CurrentNode
          ProcessNode(Child,CurrentSum)

好吧，这为您提供了从根开始的路径。然而，你可以做一个小小的改变:

    for all Children of CurrentNode
          ProcessNode(Child,CurrentSum)
          ProcessNode(Child,0)

您可能需要考虑一下(我忙于其他事情)，但这基本上应该运行以树中每个节点为根的相同算法

编辑:这实际上只给出了“结束节点”。但是，由于这是一棵树，您可以从这些末端节点开始，然后返回，直到获得所需的总和。

编辑 2:当然，如果所有值都是正数，那么如果您当前的总和 >= 所需的总和，您可以中止下降