Как найти сумму значений узла для заданной глубины в двоичном дереве?

С рекурсией это будет легко:

int calc_sum(node, depth)
{
  if (depth > 0)
  {
    sum = 0   
    for every children n of node
      sum += calc_sum(n, depth -1)
    return sum
  }
  else
    return node.value
}

Это вычислит частичную сумму на глубине d дерева t Как сумму значений t.children на глубине d-1. Как будто вам было интересно, вы сводите оставшуюся глубину вместе с поддеревом, которое вы вычисляете в качестве параметра. Если вы хотите получить более эффективное решение, вы можете использовать динамическое программирование для решения этой проблемы итерационным способом.

На самом деле вы можете избежать рекурсии и по-прежнему использовать поиск по ширине. Способ сделать это-сохранить уровень (глубину) каждого узла. Изначально вы просто устанавливаете уровень корня равным 0. Теперь, при выполнении BFS, когда вы перемещаетесь из узла u в узел v, вы устанавливаете depth[v] = depth[u] + 1. Чтобы сохранить глубину, вы либо используете обычный массив, либо добавляете еще один дополнительный элемент в очередь BFS. Вот псевдокод функции, которая находит сумму значений узлов на глубине d в двоичном дереве с n узлы, где я добавил еще один элемент в очередь, чтобы представить глубину:

int findSum(d) { 

    ans = 0;
    q = new Queue(); //define the queue
    q.push(root, 0); //insert the root, which has depth 0.

    while(! q.empty()) {
        current_node = q.top().first, current_depth = q.top().second; //Get the current node and its depth
        q.pop(); //remove the current node from the queue

        if(current_depth == d)
            ans += current_node -> value; //if the current node is on the required depth, then add its value to the answer

        if(current_node -> left != NULL)
            q.push(current_node -> left, current_depth + 1); //add the left child to the queue, which has a depth of one more than the current depth

        if(current_node -> right != NULL)
            q.push(current_node -> right, current_depth + 1); //add the right child to the queue, which has a depth of one more than the current depth
    }
    return ans;
}

int sum(Node node , int Level)

`{ if(level==depth)
        return Level;
    else
    return ( sum(node.left, Level+1), sum(node.right, Level+1)`}

Вот нечто подобное, что я должен был реализовать для вопроса интервью. Надеюсь, это поможет.

//Can you write me a function that returns an array of all the averages of the nodes 
//at each level (or depth)??


BinarySearchTree.prototype.nodeAverages = function() {
    var node = this.root;
    var result = {};
    var depthAverages = [];

    var traverse = function(node, depth) {
        if (!node) return null;
        if (node) {
            if (!result[depth])
                result[depth] = [node.value];
            else
                result[depth].push(node.value);
        }
        //check to see if node is a leaf, depth stays the same if it is
        //otherwise increment depth for possible right and left nodes
        if (node.right || node.left) {
            traverse(node.left, depth + 1);
            traverse(node.right, depth + 1);
        }
    };
    traverse(node, 0);

    //get averages and breadthFirst
    for (var key in result) {
        var len = result[key].length;
        var depthAvg = 0;
        for (var i = 0; i < len; i++) {
            depthAvg += result[key][i];
        }
        depthAverages.push(Number((depthAvg / len).toFixed(2)));
    }
    return depthAverages;
};

//Tests
var bst = new BinarySearchTree();
bst.add(10).add(20).add(30).add(5).add(8).add(3).add(9).add(7).add(50).add(80).add(98);
console.log(bst.nodeAverages()); //[ 10, 12.5, 13.67, 22, 80, 98 ]

    public static void LevelSum(Node root, int level)
    {
        Queue<Node> q = new Queue<Node>();
        q.Enqueue(root);
        --level;

        while (true)
        {
            int count = q.Count;
            while (count > 0 && level > 0)
            {
                var temp = q.Dequeue();
                if (temp.Left != null)
                    q.Enqueue(temp.Left);
                if (temp.Right != null)
                    q.Enqueue(temp.Right);
                count--;
            }
            if (level == 0)
            {
                count = q.Count;
                var sum = 0;
                while (count > 0)
                {
                    sum += q.Dequeue().data;
                    count--;
                }
                Console.WriteLine(sum);
                return;
            }
            else if (level > 0)
                level--;
            else
                return;
        }
    }

Простой рекурсивный алгоритм. Текущий уровень всегда дает 0 при вызове метода.

public int SumSameLevelNodes(int levelToFind, int currentLevel)
    {
        if (this == null)
            return 0;
        int sum = 0;
        if (currentLevel == levelToFind)
            sum = this.value;
        if (this.lNode != null && currentLevel < levelToFind)
        {
            sum += lNode.SumSameLevelNodes(levelToFind, currentLevel + 1);
        }
        if (this.rNode != null && currentLevel < levelToFind)
        {
            sum += rNode.SumSameLevelNodes(levelToFind, currentLevel + 1);
        }
        return sum;
    }