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

Question

以下是一个采访问题。

您将获得一个二叉树（不一定是BST），其中每个节点都包含一个值。设计一个算法来打印所有总计为该值的路径。注意，它可以是树中的任何路径-它不必从根开始。

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

Answer 1

基于上面Christian的回答：

public void printSums(Node n, int sum, int currentSum, String buffer) {
     if (n == null) {
         return;
     }
     int newSum = currentSum + n.val;
     String newBuffer = buffer + " " + n.val;
     if (newSum == sum) {
         System.out.println(newBuffer);
     }
     printSums(n.left, sum, newSum, newBuffer);
     printSums(n.right, sum, newSum, newBuffer);
     printSums(n.left, sum, 0, "");
     printSums(n.right, sum, 0, "");
} 

printSums(root, targetSum, 0, "");

Answer 2

这里有一个O（n numResults）答案（基本上与@某人的答案相同，但所有问题都已解决）：

1. 对二叉树进行前序、按序或后序遍历。
2. 在进行遍历时，维护从根节点到当前节点上方节点的节点值的累积和。让我们将此值称为累积量SumBeforeNode。
3. 当您在遍历中访问一个节点时，将其添加到key的哈希表中（该key的值将是节点列表）。
4. 计算umulativeSumBeforeNode和目标总和之间的差异。在哈希表中查找此差异。
5. 如果哈希表查找成功，它应该生成一个节点列表。这些节点中的每一个都代表解决方案的开始节点。当前节点代表每个相应开始节点的结束节点。将每个[开始节点，结束节点]组合添加到您的答案列表中。如果哈希表查找失败，则什么都不做。
6. 在遍历中访问完一个节点后，从哈希表中存储在keyumulativeSumBeforeNode的列表中删除该节点。

代码：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class BinaryTreePathsWithSum {
    public static void main(String[] args) {
        BinaryTreeNode a = new BinaryTreeNode(5);
        BinaryTreeNode b = new BinaryTreeNode(16);
        BinaryTreeNode c = new BinaryTreeNode(16);
        BinaryTreeNode d = new BinaryTreeNode(4);
        BinaryTreeNode e = new BinaryTreeNode(19);
        BinaryTreeNode f = new BinaryTreeNode(2);
        BinaryTreeNode g = new BinaryTreeNode(15);
        BinaryTreeNode h = new BinaryTreeNode(91);
        BinaryTreeNode i = new BinaryTreeNode(8);

        BinaryTreeNode root = a;
        a.left = b;
        a.right = c;
        b.right = e;
        c.right = d;
        e.left = f;
        f.left = g;
        f.right = h;
        h.right = i;

        /*
                5
              /   \
            16     16
              \     \
              19     4
              /
             2
            / \
           15  91
                \
                 8
        */

        List<BinaryTreePath> pathsWithSum = getBinaryTreePathsWithSum(root, 112); // 19 => 2 => 91

        System.out.println(Arrays.toString(pathsWithSum.toArray()));
    }

    public static List<BinaryTreePath> getBinaryTreePathsWithSum(BinaryTreeNode root, int sum) {
        if (root == null) {
            throw new IllegalArgumentException("Must pass non-null binary tree!");
        }

        List<BinaryTreePath> paths = new ArrayList<BinaryTreePath>();
        Map<Integer, List<BinaryTreeNode>> cumulativeSumMap = new HashMap<Integer, List<BinaryTreeNode>>();

        populateBinaryTreePathsWithSum(root, 0, cumulativeSumMap, sum, paths);

        return paths;
    }

    private static void populateBinaryTreePathsWithSum(BinaryTreeNode node, int cumulativeSumBeforeNode, Map<Integer, List<BinaryTreeNode>> cumulativeSumMap, int targetSum, List<BinaryTreePath> paths) {
        if (node == null) {
            return;
        }

        addToMap(cumulativeSumMap, cumulativeSumBeforeNode, node);

        int cumulativeSumIncludingNode = cumulativeSumBeforeNode + node.value;
        int sumToFind = cumulativeSumIncludingNode - targetSum;

        if (cumulativeSumMap.containsKey(sumToFind)) {
            List<BinaryTreeNode> candidatePathStartNodes = cumulativeSumMap.get(sumToFind);

            for (BinaryTreeNode pathStartNode : candidatePathStartNodes) {
                paths.add(new BinaryTreePath(pathStartNode, node));
            }
        }

        populateBinaryTreePathsWithSum(node.left, cumulativeSumIncludingNode, cumulativeSumMap, targetSum, paths);
        populateBinaryTreePathsWithSum(node.right, cumulativeSumIncludingNode, cumulativeSumMap, targetSum, paths);

        removeFromMap(cumulativeSumMap, cumulativeSumBeforeNode);
    }

    private static void addToMap(Map<Integer, List<BinaryTreeNode>> cumulativeSumMap, int cumulativeSumBeforeNode, BinaryTreeNode node) {
        if (cumulativeSumMap.containsKey(cumulativeSumBeforeNode)) {
            List<BinaryTreeNode> nodes = cumulativeSumMap.get(cumulativeSumBeforeNode);
            nodes.add(node);
        } else {
            List<BinaryTreeNode> nodes = new ArrayList<BinaryTreeNode>();
            nodes.add(node);
            cumulativeSumMap.put(cumulativeSumBeforeNode, nodes);
        }
    }

    private static void removeFromMap(Map<Integer, List<BinaryTreeNode>> cumulativeSumMap, int cumulativeSumBeforeNode) {
        List<BinaryTreeNode> nodes = cumulativeSumMap.get(cumulativeSumBeforeNode);
        nodes.remove(nodes.size() - 1);
    }

    private static class BinaryTreeNode {
        public int value;
        public BinaryTreeNode left;
        public BinaryTreeNode right;

        public BinaryTreeNode(int value) {
            this.value = value;
        }

        public String toString() {
            return this.value + "";
        }

        public int hashCode() {
            return Integer.valueOf(this.value).hashCode();
        }

        public boolean equals(Object other) {
            return this == other;
        }
    }

    private static class BinaryTreePath {
        public BinaryTreeNode start;
        public BinaryTreeNode end;

        public BinaryTreePath(BinaryTreeNode start, BinaryTreeNode end) {
            this.start = start;
            this.end = end;
        }

        public String toString() {
            return this.start + " to " + this.end;
        }
    }
}

Answer 3

这是一棵树，不是一个图。所以，你可以这样做：

伪代码：

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：当然，如果所有值都为正，那么如果当前总和为，则可以中止下降