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

Question

以下是面试问题.

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

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

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:当然,如果所有值都是正数,那么如果当前总和> =所需的值,则可以中止下降

Answer 2

这是一个O(n + numResults)答案(基本上与@ Somebody的答案相同,但解决了所有问题):

1. 执行二叉树的预订,按顺序或后序遍历.
2. 在进行遍历时,请维护从根节点到当前节点上方节点的节点值的累积和.我们称之为这个值cumulativeSumBeforeNode.
3. 当您访问遍历中的节点时,将其添加到密钥的哈希表中cumulativeSumBeforeNode(该密钥的值将是节点列表).
4. 计算cumulativeSumBeforeNode目标总和之间的差异.在哈希表中查找这个差异.
5. 如果哈希表查找成功,它应该生成一个节点列表.这些节点中的每一个都代表解决方案的起始节点.当前节点表示每个对应的起始节点的结束节点.将每个[开始节点,结束节点]组合添加到答案列表中.如果哈希表查找失败,则不执行任何操作.
6. 在遍历遍历遍历中访问节点后,从存储在cumulativeSumBeforeNode哈希表中的键的列表中删除该节点.

码:

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

基于克里斯蒂安的答案:

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, "");