バイナリツリーの平衡合計

Question

興味深いアルゴリズム上の問題が見つかりました。葉を除くすべての頂点に値0を持つバイナリツリーが与えられます。葉では、2つのオプションがあります。

1. 値は不明であるが、しかし、我々はそれが> = 1つの

2. 値が知られている自然数で知っていて、それが自然数> = 1

です

問題は、ツリーの各サブツリーが左右のサブツリーの頂点で同じ値の合計を持つように、葉のすべての未知の値を設定できるかどうかを判断することです。例えば

：

tree1という：

 0 
    /\ 
    0 ? 
/\ 
    0 5 
/\ 
? ? 

答えはNOである - すべての疑問符が自然数である必要があり、それはもちろん

不可能であることを考慮して

tree2：

 0 
    / \ 
    0  0 
/\ /\ 
    0 10 ? ? 
/\ 
5 ? 

答えはYESです - すべての疑問符にそれぞれ5,10,10を設定します。

これまでのところ、私は明らかなアルゴリズムしか思い出せませんでした。線形方程式のシステムを作成し、それが自然数の解を持つかどうかを調べます。しかし、私はそれが大きな木のために非常に遅くなる可能性があり、それを解決するためのより良い方法でなければならないと思います。誰でも助けることができますか？私は非常に感謝されます。

Answer 1

私は再帰的な解決策はうまく動作すると思います。すべてのノードで、左右の子の重みを取得します。

1. LとRの両方が知られている：あなたは、次の例を持っているノードが有効なのIFF L == R
2. どちらもLであるか、Rが知られている：このノードが不明であり、二回のことを多重 を持っていますLとRの最大の多重度
3. LまたはRのいずれかが不明です。このノードは、既知の子の の重みが、未知の子 の倍数で割り切れる場合に有効です。体重は既知の子供の体重の2倍です。

ここでのアイデアは、値が整数にすぎないので、未知の子供が特定のノードの下にあるかどうかを把握する必要があるということです。 1つのノードで、左の子が4つの未知数を有し、その右に1つの未知数がある場合でも、1つの未知数は4の倍数でなければならないため、このノードの多重度は8である必要があるため、

注：私はここで多重度という言葉を使用していますが、実際にはそれほど正しいとは言えませんが、私は良い言葉を使うことはできません。ここで

あなたの例で、このソリューションを示しゴー内のコード、です：あなたは、常にコードブロックのツリーを描くしようとすることができます

package main 

import (
    "fmt" 
) 

// Assume that (Left == nil) == (Right == nil) 
type Tree struct { 
    Val   int 
    Left, Right *Tree 
} 

func (t *Tree) GetWeight() (weight int, valid bool) { 
    if t.Left == nil { 
    return t.Val, true 
    } 
    l, lv := t.Left.GetWeight() 
    r, rv := t.Right.GetWeight() 
    if !lv || !rv { 
    return 0, false 
    } 
    if l < 0 && r < 0 { 
    if l < r { 
     return 2 * l, true 
    } 
    return 2 * r, true 
    } 
    if l < 0 { 
    return 2 * r, r%(-l) == 0 
    } 
    if r < 0 { 
    return 2 * l, l%(-r) == 0 
    } 
    return r + l, r == l 
} 

func main() { 
    t := Tree{0, 
    &Tree{0, 
     &Tree{0, 
     &Tree{Val: 5}, 
     &Tree{Val: -1}, 
     }, 
     &Tree{Val: 10}, 
    }, 
    &Tree{0, 
     &Tree{Val: -1}, 
     &Tree{Val: -1}, 
    }, 
    } 
    w, v := t.GetWeight() 
    fmt.Printf("%d, %t\n", w, v) 
    t = Tree{0, 
    &Tree{0, 
     &Tree{0, 
     &Tree{Val: -1}, 
     &Tree{Val: -1}, 
     }, 
     &Tree{Val: 5}, 
    }, 
    &Tree{Val: -1}, 
    } 
    w, v = t.GetWeight() 
    fmt.Printf("%d, %t\n", w, v) 
} 

Answer 2

これは並列化可能です。葉から根まで方程式のシステムを作成し、各頂点で方程式（および計算）をマージします。方程式系が不可能になると、すべての計算を打ち切ります。

この非並列アナログは、短絡評価です。