找到二叉树最便宜的路径？

Question

我正在努力为以下问题找到算法:

给定一个整数的二叉树,分支(也就是从根开始并到达叶节点的分支)的成本由其值的总和给出.编写一个返回最便宜分支列表的函数.

任何人都可以向我推荐完成此练习的最简单方法吗？

Answer 1

它可以很容易地递归完成.该函数打印所有根到叶子路径以及最便宜的分支.我使用Arraylist将所有节点从root添加到leaf.每当到达叶子节点时,我只检查到目前为止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

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

希望这可以帮助！