search - 如何在二叉树中找到给定深度的节点值的总和？

Question

我已经为此挠头好几个小时了......

问题:

Binary Tree

   (0)      depth 0
   / \
  10   20   depth 1
 / \   / \
30 40  50 60  depth 2

我正在尝试编写一个函数，该函数将深度作为参数并返回给定深度的节点值的总和。

例如，如果我通过 2，它应该返回 180(即 30+40+50+60)

我决定使用广度优先搜索，当我找到所需深度的节点时，
总结值(value)，但我就是不知道如何找出哪个节点在什么深度的方式。
但是通过这种方法，我觉得要走完全错误的方向。

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 ++;
}

}

Answer 1

只需递归地进行深度优先搜索，保持当前级别并对给定深度的节点求和。

伪代码:

sum(Node, Level) = 
  if (Level == 0) return Node.value;
  else return f(Node.left, Level-1) + 
              f(Node.right, Level-1).