1

说明：对于给定的二叉树

              +---+
              | 9 |
              +---+
             /     \
         +---+     +---+
         | 7 |     | 6 |
         +---+     +---+
        /     \         \
    +---+     +---+     +---+
    | 3 |     | 2 |     | 4 |
    +---+     +---+     +---+
             /               \
         +---+               +---+
         | 5 |               | 2 |
         +---+               +---+

总和将计算为：

1 * 9 + 2 * (7 + 6) + 3 * (3 + 2 + 4) + 4 * (5 + 2) = 90

我解决这个问题的方法是找到每个节点的级别，将其与节点的键相乘，并对左右子树中的所有节点递归执行。

int weightedSumAtAllLevels(BTNode node) {
    if (node != null)
        return levelSumOfLeftSubTree(node.getLeftChild())
                + levelSumOfRightSubTree(node.getRightChild())
                + node.getKey();
    else
        return 0;
}

int levelSumOfLeftSubTree(BTNode tmp) {
    if (tmp == null) {
        return 0;
    } else {
        int level = levelOfNode(tmp);
        return level * tmp.getKey()
                + levelSumOfLeftSubTree(tmp.getLeftChild());

    }
}

int levelSumOfRightSubTree(BTNode tmp) {
    if (tmp == null) {
        return 0;
    } else {
        int level = levelOfNode(tmp);
        return level * tmp.getKey()
                + levelSumOfRightSubTree(tmp.getRightChild());
    }
}
int levelOfNode(BTNode node) {
    if (node == null)
        return 0;
    else
        return 1 + levelOfNode(node.getParent());
 }

它似乎不起作用。我知道这个解决方案有缺陷，但我无法修复它。有什么帮助吗？建议？

4

3 回答 3

2

主要问题是，一旦你开始向左走，你就会一直向左走。你从不看左孩子的右孩子，反之亦然。

您可以使用一个同时接受节点及其级别的函数来计算加权和。这将极大地简化实施，使其更容易正确。

这是一个近似的实现（我没有测试过）：

int weightedSumAtAllLevels(BTNode node, int level) {
    if (node != null) {
        return level * node.getKey() +
               weightedSumAtAllLevels(node.getLeftChild(), level + 1) +
               weightedSumAtAllLevels(node.getRightChild(), level + 1);
    } else {
        return 0;
    }
}

我把它作为一个练习来弄清楚应该如何为根节点调用它。

于 2013-10-26T07:20:07.277 回答
1

只需从根开始并初始化级别 = 1。

sum = root.key()*level + weightedSum( root.left(), level + 1 ) + weightedSum( root.right(), level + 1 );
于 2013-10-26T07:21:12.570 回答
0

提示.. 对树进行 DFS 遍历。然后对于每个深度求和节点的值并乘以深度+1。

于 2013-10-26T07:19:41.103 回答