G家练习

Water Drop & Leaves

Water drop from root of a tree and each tree node contains several branches. It takes certain amount of time for water to drop from one node to another. Calculate the shortest time takes for water to cover all leaves.

这题其实是求从Root到底最长的边，就是把值往下传，传到底求global max。

int max = Integer.MIN_VALUE;
public int LongestPathFromRootToEnd(TreeNode root) {
    if (root == null) return 0;
    helper(root, 0);
    return max;
}

private void helper(TreeNode root, int curtVal) {
    if (root.children.length == 0)  {
        max = Math.max(max, curtVal);
        return;
    }
    for (int i = 0; i < root.children.length; i++) {
        if (root.children[i] != null) {
            helper(root.children[i], curtVal + root.edgeVal[i]);
        }
    }
}

Follow-Up 2: What if it is a graph instead of a tree? One TreeNode can link to another one in many ways:

Follow-up

单方向图找最长边，用Toplogical Sort。先把所有的点通过toplogical order走一遍，每个点包含一个Integer.MIN_VALUE的值，然后更新为root到这个点的最长边的值。

Longest Path in a Directed Acyclic Graph - GeeksforGeeksGeeksforGeeks

Rooms and Keys

Build City on a Highway