algorithm - 二分木の平衡和

Question

興味深いアルゴリズムの問題を見つけました。葉を除くすべての頂点の値が 0 である二分木が与えられます。リーフには 2 つのオプションがあります。

値は不明ですが、自然数 >=1 であることはわかっています
値が既知で、自然数 >=1 である

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

例えば：

ツリー1:

答えは NO です。すべての疑問符が自然数でなければならないことを考慮すると、もちろん不可能です。

ツリー 2:

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

答えは YES です。すべてのクエスチョンマークにそれぞれ 5、10、10 を設定します。

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

score 2 · Accepted Answer

これは並列化可能です。葉から根に向かって連立方程式を作成し、各頂点で方程式 (および計算) をマージします。連立方程式が不可能になったら、すべての計算を中止します。

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

score 2 · Accepted Answer

再帰的な解決策は問題なく機能すると思います。すべてのノードで、左右の子の重みを取得します。次のケースがあります。

L と R は両方とも既知です: ノードは L == R の場合に有効です
L も R も不明: このノードは不明であり、L と R の最大の多重度の 2 倍の多重度を持っています。
L または R のいずれかが不明: このノードは、既知の子の重みが未知の子の多重度で割り切れる場合に有効です。その体重は既知の子供の体重の 2 倍です。

ここでの考え方は、値は整数のみであるため、特定のノードの下にある未知の子の数を追跡する必要があるということです。多重度は常に 2 倍になります。1 つのノードで、その左の子に 4 つの未知数があり、その右の子に 1 つの未知数がある場合でも、1 つの未知数は 4 の倍数でなければならないため、このノードの多重度は 8 である必要があります。

注: ここでは多重度という言葉を使用していますが、それはあまり正しくありませんが、使用する適切な言葉が思い浮かびませんでした。

あなたの例でこのソリューションを示すGoのコードは次のとおりです。

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)
}

algorithm - 二分木の平衡和

2 に答える 2

Related

Reference