問題描述

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

已知類定義如下

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

輸入node滿足以下條件：1 node的value是大于0的浮點數(shù)2 node的下級節(jié)點（以及更下級節(jié)點）的value可能是null或者大于0的浮點數(shù)程序的作用如下：1 將樹形結(jié)構(gòu)里面所有value是null的均設(shè)為大于0的浮點數(shù)2 非葉子節(jié)點（即children數(shù)量大于0的節(jié)點）的value均等于它的children的value之和

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

示例解答

這個問題要如何解答？

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

問題解答

沒有寫具體代碼，說一下思路吧首先，把問題分為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é)點們?nèi)シ指腹?jié)點的值減去這部分確定的值的和（題目的要求）。然后如果不是葉節(jié)點的節(jié)點按照上述方法遞歸。

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

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

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

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