【Lintcode】1403. Maximum Product Path

题目地址：

https://www.lintcode.com/problem/maximum-product-path/description

给定一个二叉树，每个节点有一个权值，问从树根到叶子的路径中，节点权值之积模$10^9+7$最大的积是多少。

直接DFS即可。一边DFS一边记录达到当前节点的路径的节点权值积是多少，到达叶子的时候更新答案。代码如下：

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;public class Solution {
    private int res;private int MOD = (int) (1e9 + 7);/*** @param x: The end points of edges set* @param y: The end points of edges set* @param d: The weight of points set* @return: Return the maximum product*/public int getProduct(int[] x, int[] y, int[] d) {
    // Write your code here// 邻接表建图Map<Integer, Set<Integer>> graph = buildGraph(x, y);res = Integer.MIN_VALUE;dfs(0, 1, graph, d, new boolean[graph.size()]);return res;}private void dfs(int cur, long prod, Map<Integer, Set<Integer>> graph, int[] d, boolean[] visited) {
    prod *= d[cur];prod %= MOD;if (prod < 0) {
    prod += MOD;}visited[cur] = true;// isLeaf记录cur是否是叶子节点。当cur没有未访问的邻居的时候，其就是叶子节点boolean isLeaf = true;for (int next : graph.get(cur)) {
    if (!visited[next]) {
    isLeaf = false;dfs(next, prod, graph, d, visited);}}// 如果是叶子节点，则更新答案if (isLeaf) {
    res = (int) Math.max(res, prod);}}private Map<Integer, Set<Integer>> buildGraph(int[] x, int[] y) {
    Map<Integer, Set<Integer>> graph = new HashMap<>();for (int i = 0; i < x.length; i++) {
    graph.putIfAbsent(x[i] - 1, new HashSet<>());graph.putIfAbsent(y[i] - 1, new HashSet<>());graph.get(x[i] - 1).add(y[i] - 1);graph.get(y[i] - 1).add(x[i] - 1);}return graph;}
}

时空复杂度$O(n)$。