为了这个我已经挠了好几个小时了……
problem:
Binary Tree
(0) depth 0
/ \
10 20 depth 1
/ \ / \
30 40 50 60 depth 2
我正在尝试编写一个函数,该函数以深度为参数并返回给定深度的节点值的总和。
例如,如果我通过 2,它应该返回 180(即 30+40+50+60)
我决定使用广度优先搜索,当我找到具有所需深度的节点时,
总结该值,但我只是不知道如何找出哪个节点处于什么深度。
但通过这种方法,我感觉自己走向了完全错误的方向。
function level_order($root, $targetDepth) {
$q = new Queue();
$q->enqueue($root);
while(!$q->isEmpty) {
//how to determin the depth of the node???
$node = $q->dequeue();
if($currentDepth == $targetDepth) {
$sum = $node->value;
}
if($node->left != null) {
$q->enqueue($node->left);
}
if($node->right != null) {
$q->enqueue($node->right);
}
//need to reset this somehow
$currentDepth ++;
}
}
只需递归地进行深度优先搜索,保持当前级别并对给定深度的节点求和。
伪代码:
sum(Node, Level) =
if (Level == 0) return Node.value;
else return f(Node.left, Level-1) +
f(Node.right, Level-1).
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)