二叉樹中的平衡和數

我發現了一個有趣的算法問題。我們得到一個二叉樹，它的每一個頂點的值都是0，除了葉子。在葉，我們有兩種選擇：二叉樹中的平衡和數

值是未知的，但我們知道這是一個自然數> = 1個
值是已知的，它是一個自然數> = 1

問題是要確定是否有可能在樹葉中設置每個未知值，使得給定樹的每個子樹在其左右子樹的頂點中具有相同的值總和。

例如：

樹1：

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

答案是否定的 - 考慮到每一個問號必須是一個自然數，它當然不可能

tree2：

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

答案是YES - 我們在每個問號中分別設置5,10,10。到目前爲止，我只想出了一個明顯的算法 - 我們創建了線性方程組，並檢查它是否有自然數的解。但是我認爲對於大樹來說它可能會非常緩慢，應該是解決它的更好方法。任何人都可以幫忙嗎？我會很感激。

來源

2012-07-21 xan

你總是可以嘗試繪製樹在一個代碼塊：| – Alexander 2012-07-21 21:38:36

不會創建一個大的方程組，而是創建小的方程組，解決它們，然後填充結果並搜索下一個子問題。 – 2012-07-21 23:50:03

我認爲遞歸解決方案工作得很好。在每個節點都可以獲得左右兒童的重量。您有以下情況：

L和R都知道：該節點是有效的當且僅當大號== [R
無論是L或R是已知的：該節點是未知的，具有多重兩倍的L和R的最大重數
L或R中的一個是未知數：如果已知子的權重可由未知子的整數倍整除，則此節點有效。它的體重是已知孩子體重的兩倍。

這裏的想法是，你需要跟蹤有多少未知的孩子在某個節點下面，因爲值只能是整數。多重性總是雙倍的，因爲在一個節點上，即使其左邊的孩子有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) 
}

來源

2012-07-22 00:06:31

非常感謝！聰明的遞歸是我所需要的。創建方程組似乎太困難了。 – xan 2012-07-22 11:10:31

這是可並行化的。您可以從葉子到根部創建方程組，合併每個頂點的方程（和計算）。當方程組變爲不可能時，放棄所有計算。

這是一個非平行的模擬，這將是短路評估。

來源

2012-07-21 21:31:41 ninjagecko

二叉樹中的平衡和數

回答

相關問題