说明:对于给定的二叉树
+---+
| 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());
}
它似乎不起作用。我知道这个解决方案有缺陷,但我无法修复它。有什么帮助吗?建议?