二叉树中的平衡和数

我发现了一个有趣的算法问题。我们得到一个二叉树，它的每一个顶点的值都是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

二叉树中的平衡和数

回答

相关问题