在二叉树中打印具有给定总和的所有路径的算法 [英] Algorithm to print all paths with a given sum in a binary tree

问题描述

以下是面试问题.

为您提供了一个二叉树(不一定是BST)，其中每个节点都包含一个值. 设计一种算法来打印所有总计为该值的路径. 请注意，它可以是树中的任何路径-不必开始 在根上.

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.

尽管我能够找到树中从根开始的所有路径都有给定的总和，但是对于不是从根开始的路径，我却无法做到.

Although I am able to find all paths in tree that start at the root have the given sum, I am not able to do so for paths not not starting at the root.

推荐答案

好吧，这是一棵树，而不是图.因此，您可以执行以下操作:

Well, this is a tree, not a graph. So, you can do something like this:

伪代码:

global ResultList

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

好吧，这为您提供了从根开始的路径.但是，您可以做一个很小的更改:

Well, this gives you the paths that start at the root. However, you can just make a tiny change:

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

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

You might need to think about it for a second (I'm busy with other things), but this should basically run the same algorithm rooted at every node in the tree

这实际上仅给出了结束节点".但是，由于这是一棵树，因此您可以仅从这些末端节点开始然后向后走，直到获得所需的总和.

this actually gives the "end node" only. However, as this is a tree, you can just start at those end nodes and walk back up until you get the required sum.

当然，如果所有值都为正，那么如果当前总和> =所需值，则可以中止下降

EDIT 2: and, of course, if all values are positive then you can abort the descent if your current sum is >= the required one

这篇关于在二叉树中打印具有给定总和的所有路径的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！