algorithm - 二叉树中的平衡和

Question

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

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

2. 已知值为自然数>=1

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

例如:

树 1:

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

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

树2:

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

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

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

Answer 1

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

1. L 和 R 都已知:节点有效当且仅当 L == R
2. Neither L or R is known:这个节点是未知的并且具有多重性L和R最大重数的两倍
3. L 或 R 中的一个是未知的:这个节点是有效的当且仅当已知 child 的体重可以被不知名的 child 。它的体重是已知 child 体重的两倍。

这里的想法是，您需要跟踪某个节点下有多少个未知子节点，因为值只能是整数。重数总是加倍，因为在一个节点，即使它的左子节点有 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)
}