java - 多叉樹求值，程式高手，演算法高手看過來

Question

遇到一道筆試題，完全沒思路，求助。 。 。 。

已知類別定義如下

class Node {
    public Double value;
    public List<Node> children;
}

輸入node滿足以下條件：
1 node的value是大於0的浮點數
2 node的下級節點（以及更下級節點）的value可能是null或大於0的浮點數
程式的作用如下：
1 將樹狀結構裡面所有value是null的均設為大於0的浮點數
2 非葉子節點（即children數量大於0的節點）的value均等於它的children的value之和

public void doit(Node node){
    ......
}

範例

答案

#這個問題要如何解答？

已經有高手答出來了，綜合一下下面兩人的答案就是完美答案。其實就是我採納那個答案裡面把均分改為隨機就很完美了

Answer 1

沒有寫具體程式碼，說一下思路吧
首先，把問題分為2步
Step1、確定非葉子節點的值
Step2、確定葉子節點的值
先處理Step1，處理完Step1之後，Step2就不用多說了，根據父節點的數值均分即可。
對於Step1，
step1-1： 由下向上遍歷各個非葉子節點，透過對其子節點求和，確定其最小值。如最右側的子樹，最小值為5.5。
step1-2： 由上向下，逐層確定非葉子節點，為方面描述，命名[100]為第一層，[10，20，?，?]為第二層，以此類推。根據step1-1的結果，第二層的最小值為[10，20，>60,>5.5],將100減去最小值之和，然後均分，結果為[10，20，62.25，7.75]
step1-3： 同上，確定第三層，結果為[5.5, 4.5] [9.5, 5.25, 5.25] [60, 1.125, 1.125] [6.625，1.125]
這裡最後一組較特別，需要考慮到7.分配的時候，其左下已經有5.5了，所以7.75裡面可自由支配的數為7.75-5.5=2.25，將2.25均分到兩邊，結果[6.625，1.125]
step1-4： 最後一層相信不用再囉嗦了，其實就是step2，均分下來就好。

Answer 2

剛剛看了一下這題目，覺得很有意思。然後思考了一下，提出以下問題。
我的思路的話就是遞歸。

1. 分層次遍歷，在每層的時候把確定的值加起來，為空的節點們去分父節點的值減去這部分確定的值的和（題目的要求）。然後如果不是葉節點的節點依照上述方法遞歸。

2. 但是確定每個節點的值得時候，如某些葉子節點的時候，我們需要隨機給他們賦值，他們的值有些受到父節點約束，有些不收父節點約束比如第二層的第三個節點的兩個葉子節點，如果我們賦給他們的值使得他們的父節點不滿足要求了，這就不符合題意了。所以我想的是每次確定值得時候傳入這些節點的值範圍。這些範圍的確定又會導致一些問題，問題又會變得複雜。

3. 範圍確定，每個空節點的最大值肯定是父節點的值減去同行子節點的值的和，最小取值肯定是大於其子節點的有值元素的和。因為只有確定了某個範圍，其葉子節點的一些隨機值的取法不會導致其餘節點不符合題意。總的意思來說每個同父節點的空節點的取值互相有約束，其中一個節點的取值雖然滿足自身，但是會​​使得其餘節點不滿足要求。舉例：
   

如果這樣取值，則局部滿足，會導致其他節點的取值不滿足要求。所以在沒約束的情況下可能會導致意想不到的結果。我們需要去確定這些範圍。

綜上，這只是我的一些思考後的一些想法，也許有錯誤的地方歡迎指正。