多叉樹求值問題
這是一篇來自segmentfault的問題
一 問題描述
已知類定義如下
class Node {
public Double value;
public List<Node> children;
}
輸入node滿足以下條件：
- node的value是大于0的浮點數(shù)
- node的下級節(jié)點（以及更下級節(jié)點）的value可能是null或者大于0的浮點數(shù)
程序的作用如下：
- 將樹形結(jié)構(gòu)里面所有value是null的均設(shè)為大于0的浮點數(shù)
- 非葉子節(jié)點（即children數(shù)量大于0的節(jié)點）的value均等于它的children的value之和
public void doit(Node node){
......
}
示例
解答
二 算法思路
1 想法
分層次遍歷，在每層的時候把確定的值加起來，為空的節(jié)點們?nèi)シ指腹?jié)點的值減去這部分確定的值的和（題目的要求）。然后如果不是葉節(jié)點的節(jié)點按照上述方法遞歸。
但是確定每個節(jié)點的值得時候，如某些葉子節(jié)點的時候，我們需要隨機給他們賦值，他們的值有些受到父節(jié)點約束，有些不收父節(jié)點約束比如第二層的第三個節(jié)點的兩個葉子節(jié)點，如果我們賦給他們的值使得他們的父節(jié)點不滿足要求了，這就不符合題意了。所以我想的是在每次確定值得時候傳入這些節(jié)點的取值范圍。這些范圍的確定又會導致一些問題，問題又會變得復雜。
范圍確定，每個空節(jié)點的最大值肯定是父節(jié)點的值減去同行子節(jié)點的值的和，最小取值肯定是大于其子節(jié)點的有值元素的和。因為只有確定了某個范圍，其葉子節(jié)點的一些隨機值的取法不會導致其余節(jié)點不符合題意?？偟囊馑紒碚f每個同父節(jié)點的空節(jié)點的取值互相有約束，其中一個節(jié)點的取值雖然滿足自身，但是會使得其余節(jié)點不滿足要求。舉個例子：
如果這樣取值，則局部滿足，會導致其他節(jié)點的取值不滿足要求。所以在沒約束的情況下可能會導致意想不到的結(jié)果。我們需要去確定這些范圍。
ps:這是我的一個回答
另外一個答主的回答
思想和我的差不多，就是確定范圍
以下是他的回答內(nèi)容：
沒有寫具體代碼，說一下思路吧
首先，把問題分為2步
Step1、確定非葉子節(jié)點的值
Step2、確定葉子節(jié)點的值
先處理Step1，處理完Step1之后，Step2就不用多說了，根據(jù)父節(jié)點的值均分即可。
對于Step1，
step1-1： 由下向上遍歷各個非葉子節(jié)點，通過對其子節(jié)點求和，確定其最小值。如最右側(cè)的子樹，最小值為5.5。
step1-2： 由上向下，逐層確定非葉子節(jié)點，為方面描述，命名[100]為第一層，[10，20，?，?]為第二層，以此類推。根據(jù)step1-1的結(jié)果，第二層的最小值為[10，20，>60,>5.5],將100減去最小值之和，然后均分，結(jié)果為[10，20，62.25，7.75]
step1-3： 同上，確定第三層，結(jié)果為[5.5, 4.5] [9.5, 5.25, 5.25] [60, 1.125, 1.125] [6.625，1.125]
這里最后一組較特別，需要考慮到7.75分配的時候，其左下已經(jīng)有5.5了，所以7.75里面可自由支配的數(shù)為7.75-5.5=2.25，將2.25均分到兩邊，結(jié)果[6.625，1.125]
step1-4： 最后一層相信不用再羅嗦了，其實就是step2，均分下來就好。
三 總結(jié)
題目還是挺有意思的,難度不是很大,主要的還是理解題目的意思,以及考慮到各種情況。
