二叉树中的平衡和

Question

我发现了一个有趣的算法问题.我们给出了一个二叉树,它在叶子之外的每个顶点都有0值.在叶子中我们有两个选择:

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

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

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

例如:

树1:

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

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

tree2:

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

答案是肯定的 - 我们在每个问号中分别设置:5,10,10.

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

Answer 1

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

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