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

Question

Я несколько часов чесал голову за это ...

Проблема:

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

*

} * 1013

Answer 1

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

Псевдокод:

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

Answer 2

На самом деле вы можете избежать рекурсии и по-прежнему использовать поиск в ширину.Способ сделать это - сохранить уровень (глубину) каждого узла.Первоначально вы просто устанавливали уровень корня равным 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;
}

Answer 3

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

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.Как будто вам было интересно, вы сводите оставшуюся глубину вместе с поддеревом, которое вы рассчитываете как параметр.

Если вам нужно более эффективное решение, вы можете использовать динамическое программирование , чтобы решить эту проблему итеративным способом.

Answer 4

Простой рекурсивный алгоритм.Текущий уровень всегда дает 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;
    }

Answer 5

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

Answer 6

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

//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 ]

Answer 7

int sum(Node node , int Level)

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