題目描述
一棵有 n 個結(jié)點，根結(jié)點為 1 的二叉樹具温，每條邊通過兩個頂點x[i],y[i]來描述蚕涤，每個點的權(quán)值通過d[i]來描述。求從根結(jié)點到葉子結(jié)點路徑上所有結(jié)點權(quán)值乘積對1e9+7取模后最大的路徑的值铣猩。
思路點撥
從根開始遍歷揖铜，統(tǒng)計每個到根節(jié)點取模后的答案，取最大即可达皿。
考點分析
本題考查的是樹的遍歷天吓，相信大家都會判斷是否是葉節(jié)點，不過這里有個坑點就是取的是取模后的最大值峦椰，在取模時龄寞，由于有負數(shù)，需要(a * b % mod + mod) % mod汤功。
參考程序
http://www.jiuzhang.com/solution/maximum-product-path/
/**
* 本參考程序來自九章算法物邑，由 @華助教 提供。版權(quán)所有冤竹，轉(zhuǎn)發(fā)請注明出處拂封。
* - 九章算法致力于幫助更多中國人找到好的工作，教師團隊均來自硅谷和國內(nèi)的一線大公司在職工程師鹦蠕。
* - 現(xiàn)有的面試培訓(xùn)課程包括：九章算法班冒签，系統(tǒng)設(shè)計班，算法強化班钟病，Java入門與基礎(chǔ)算法班萧恕，Android 項目實戰(zhàn)班刚梭，
* - Big Data 項目實戰(zhàn)班，算法面試高頻題班, 動態(tài)規(guī)劃專題班
* - 更多詳情請見官方網(wǎng)站：http://www.jiuzhang.com/?source=code
*/
public class Solution {
/**
* @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
*/
long ans;
long mod = 1000000007;
public void dfs(int x, int f, List<List<Integer>>g, long mul,int[] d) {
int isLeaf = 1;
long now = (mul * d[x - 1] % mod + mod) % mod;
for(int i = 0; i < g.get(x).size(); i++) {
int v = g.get(x).get(i);
if(v == f) {
continue;
}
isLeaf = 0;
dfs(v, x, g, now, d);
}
if(isLeaf == 1) {
ans = Math.max(ans, now);
}
}
public int getProduct(int[] x, int[] y, int[] d) {
// Write your code here
int n = d.length;
List<List<Integer>>g = new ArrayList<List<Integer>>();
for(int i = 0; i <= x.length + 1; i++) {
g.add(new ArrayList<Integer>());
}
for(int i = 0; i < x.length; i++) {
g.get(x[i]).add(y[i]);
g.get(y[i]).add(x[i]);
}
ans = -1000000009;
dfs(1, 0, g, 1, d);
return (int)ans;
}
}
