题目地址：

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)$。