寻找二叉树中最便宜的路径？

Question

我正在努力寻找解决以下问题的算法：

给定整数二叉树，分支（也称为从根开始到达叶节点的分支）的成本由其值的总和给出。 编写一个返回最便宜分支列表的函数。

有人可以推荐我完成此练习的最简单方法吗？

Answer 1

可以很容易地递归完成。该函数打印所有从根到叶的路径以及最便宜的分支。我使用

ArrayList

添加从根到叶的所有节点。每当到达叶节点时，我只需检查到目前为止的 maxSum 是否小于当前根到叶路径并更新它。

class Node {

    public int info;
    public Node left;
    public Node right;

    public Node(int info) {
        this(info, null, null);
    }

    public Node(int info, Node left, Node right) {
        this.info = info;
        this.left = left;
        this.right = right;
    }

}

public class RootToLeaf {

    private static int maxSum = Integer.MAX_VALUE;
    private static ArrayList<Integer> finalList = new ArrayList<>();

    public static void main(String[] args) {

        Node root = new Node(8);
        root.left = new Node(4);
        root.left.left = new Node(3);
        root.left.right = new Node(1);
        root.right = new Node(5);
        root.right.right = new Node(11);
        ArrayList<Integer> list = new ArrayList<Integer>();
        path(root, list,0);
        System.out.println("Cheapest list is - " + finalList.toString() +  " and minimum sum is " + maxSum);

    }

    private static void path(Node root, ArrayList<Integer> list,int s) {

        if(root==null) {
            return;
        } else {
            list.add(root.info);
            s = s+root.info;
        }

        if ((root.left == null && root.right == null)) {
            System.out.println(list);
            if(maxSum>s) {
                maxSum = s;
                finalList = new ArrayList<>(list);
            }
            return;
        }

        path(root.left, new ArrayList<Integer>(list),s);
        path(root.right, new ArrayList<Integer>(list),s);

    }

}

输出如下：

[8, 4, 3]
[8, 4, 1]
[8, 5, 11]
Cheapest list is - [8, 4, 1] and minimum sum is 13

Answer 2

作为提示，请从树叶向上进行操作。一片叶子的成本就是叶子内部的价值。否则，从某个节点开始的最佳路径的成本由该节点的成本加上从该节点采取的最便宜路径的成本给出。你能递归地实现这个吗？

希望这有帮助！

Answer 3

您需要构建成对的priority_queue（c ++ stl有这个容器）：

• 节点索引
• 成本

成本优先，升序。

算法：

放入priority_queue对(root, cost_of_root)中。此后，循环：

1. 从priority_queue中提取对（节点，成本）
2. 如果该节点是叶子节点 - 返回对作为最佳叶子/成本。
3. 否则 - 将两对放入priority_queue：(left_son, cost + left_son.cost), (right_son, cost + right_son.cost)。

仅此而已。

Answer 4

我建议首先遍历树深度。

您将需要三个变量：

1)

current cost

，表示从根节点到当前节点的值之和。

2）从根到迄今为止任何叶子的

cheapest path

（初始化为空）

3)

cheapest cost

代表最便宜路径的成本

如果到达某个节点，请将其节点成本添加到

current cost

(1)。

如果到达叶子，请将其节点成本也添加到

current cost

。然后检查它的成本是否比

cheapest cost

（3）便宜。如果是（或者不存在最便宜的成本，因为它是您到达的第一片叶子）设置

cheapest cost = current cost

。并将

cheapest path

设置为当前路径（您可以将其存储在变量本身中，或者只是从当前离开向后遍历到根节点） 然后往上走一个节点，检查是否有你还没有访问过的分支。有的话就去检查一下。如果没有，则转到另一个节点并检查（依此类推...）

快捷键： 当你到达一个节点并且它的

current cost

大于

cheapest cost

时，你可以跳过该节点的整个子树。

Answer 5

由于树只是一种特殊的图，因此 Dijkstra 算法在这里效果很好：

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

1. 为每个节点分配一个暂定距离值：将初始节点设置为零，将所有其他节点设置为无穷大。
2. 将初始节点设置为当前节点。将所有其他节点标记为未访问。创建所有未访问节点的集合，称为未访问集。
3. 对于当前节点，考虑其所有未访问的邻居并计算它们的暂定距离。将新计算的暂定距离与当前分配的值进行比较，并分配较小的值。例如，如果当前节点 A 的距离标记为 6，并且将其与邻居 B 连接的边的长度为 2，则到 B（通过 A）的距离将为 6 + 2 = 8。如果 B 之前是标记距离大于8，则将其更改为8。否则，保持当前值。
4. 当我们考虑完当前节点的所有邻居后，将当前节点标记为已访问并将其从未访问集中删除。访问过的节点将永远不会被再次检查。
5. 如果目标节点已被标记为已访问（当规划两个特定节点之间的路线时）或者如果未访问集中的节点之间的最小暂定距离为无穷大（当规划完整的遍历时；当初始节点之间没有连接时发生）节点和剩余未访问的节点），然后停止。算法已经完成了。
6. 否则，选择暂定距离最小的未访问过的节点，将其设置为新的“当前节点”，并返回步骤3。

只需跟踪最后哪个分支的成本最低即可。返回包含该分支的列表。