問題描述

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

已知類定義如下

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

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

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

示例解答

這個(gè)問題要如何解答？

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

問題解答

沒有寫具體代碼，說一下思路吧首先，把問題分為2步Step1、確定非葉子節(jié)點(diǎn)的值Step2、確定葉子節(jié)點(diǎn)的值先處理Step1，處理完Step1之后，Step2就不用多說了，根據(jù)父節(jié)點(diǎn)的值均分即可。對(duì)于Step1，step1-1： 由下向上遍歷各個(gè)非葉子節(jié)點(diǎn)，通過對(duì)其子節(jié)點(diǎn)求和，確定其最小值。如最右側(cè)的子樹，最小值為5.5。step1-2： 由上向下，逐層確定非葉子節(jié)點(diǎn)，為方面描述，命名[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分配的時(shí)候，其左下已經(jīng)有5.5了，所以7.75里面可自由支配的數(shù)為7.75-5.5=2.25，將2.25均分到兩邊，結(jié)果[6.625，1.125]step1-4： 最后一層相信不用再羅嗦了，其實(shí)就是step2，均分下來就好。

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

分層次遍歷，在每層的時(shí)候把確定的值加起來，為空的節(jié)點(diǎn)們?nèi)シ指腹?jié)點(diǎn)的值減去這部分確定的值的和（題目的要求）。然后如果不是葉節(jié)點(diǎn)的節(jié)點(diǎn)按照上述方法遞歸。

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

范圍確定，每個(gè)空節(jié)點(diǎn)的最大值肯定是父節(jié)點(diǎn)的值減去同行子節(jié)點(diǎn)的值的和，最小取值肯定是大于其子節(jié)點(diǎn)的有值元素的和。因?yàn)橹挥写_定了某個(gè)范圍，其葉子節(jié)點(diǎn)的一些隨機(jī)值的取法不會(huì)導(dǎo)致其余節(jié)點(diǎn)不符合題意。總的意思來說每個(gè)同父節(jié)點(diǎn)的空節(jié)點(diǎn)的取值互相有約束，其中一個(gè)節(jié)點(diǎn)的取值雖然滿足自身，但是會(huì)使得其余節(jié)點(diǎn)不滿足要求。舉個(gè)例子：

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

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