5

我发现了一个有趣的算法问题。我们得到一棵二叉树，除了叶子之外，每个顶点的值都为 0。在叶子中，我们有两种选择：

  1. 值未知，但我们知道它是一个自然数 >=1

  2. 值是已知的，它是一个自然数 >=1

问题是决定是否可以设置叶子中的每个未知值，使得给定树的每个子树在其左右子树的顶点中具有相同的值总和。

例如：

树1：

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

答案是否定的——考虑到每个问号都必须是自然数，这当然是不可能的

树2：

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

答案是肯定的——我们在每个问号中分别设置：5、10、10。

到目前为止，我只提出了一个明显的算法——我们创建线性方程组并检查它是否有自然数的解。但是我认为对于大树来说它可能会很慢，这应该是解决它的更好方法。有人可以帮忙吗？我会很感激。

4

2 回答 2

2

这是可并行的。您创建从叶子到根的方程组，在每个顶点合并方程（和计算）。当方程组变得不可能时，中止所有计算。

与此类似的非并行模拟是短路评估。

于 2012-07-21T21:31:41.573 回答
2

我认为递归解决方案工作得很好。在每个节点获得左右孩子的权重。您有以下情况：

  1. L 和 R 都是已知的：节点有效当且仅当 L == R
  2. L 或 R 都不知道：这个节点是未知的，其多重性是 L 和 R 的最大多重性的两倍
  3. L 或 R 中的一个是未知的：如果已知子节点的权重可被未知子节点的倍数整除，则此节点有效。它的重量是已知孩子体重的两倍。

这里的想法是您需要跟踪某个节点下方有多少未知子节点，因为值只能是整数。多重性总是加倍，因为在一个节点上，即使它的左孩子有 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)
}
于 2012-07-22T00:06:31.410 回答