Сумма узлов в виде снизу двоичного дерева

Опубликовано: 23 Января, 2022

Учитывая двоичное дерево, задача состоит в том, чтобы вывести сумму узлов в нижнем представлении данного двоичного дерева. Вид снизу двоичного дерева - это набор узлов, видимых при просмотре дерева снизу.

Примеры:

 Вход : 
     1
    / 
   2 3
  /  
 4 5 6

Выход: 20

Вход :
        1         
       /          
      2 3         
                
         4         
                   
            5         
                      
               6

Выход: 17
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: идея заключается в использовании очереди.

  1. Поместите узлы дерева в очередь для обхода порядка уровней
  2. Начните с горизонтального расстояния (hd) 0 корневого узла, продолжайте добавлять левого дочернего элемента в очередь вместе с горизонтальным расстоянием как hd-1 и правым дочерним элементом как hd + 1.
  3. Используйте карту для хранения значения hd (как ключа) и последнего узла (как пары), имеющего соответствующее значение hd.
  4. Каждый раз, когда мы сталкиваемся с новым расстоянием по горизонтали или существующим расстоянием по горизонтали, помещаем данные узла для расстояния по горизонтали в качестве ключа. Впервые он добавится на карту, в следующий раз заменит значение. Это обеспечит присутствие на карте самого нижнего элемента для этого горизонтального расстояния.
  5. Наконец, пройдитесь по карте и вычислите сумму всех элементов.

Below is the implementation of the above approach:

C++

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Structure of binary tree
struct Node {
    Node* left;
    Node* right;
    int hd;
    int data;
};
 
// Function to create a new node
Node* newNode(int key)
{
    Node* node = new Node();
    node->left = node->right = NULL;
    node->data = key;
    return node;
}
 
// Function that returns the sum of
// nodes in bottom view of binary tree
int SumOfBottomView(Node* root)
{
    if (root == NULL)
        return 0;
    queue<Node*> q;
 
    map<int, int> m;
    int hd = 0;
    root->hd = hd;
 
    int sum = 0;
 
    // Push node and horizontal distance to queue
    q.push(root);
 
    while (q.size()) {
        Node* temp = q.front();
        q.pop();
 
        hd = temp->hd;
 
        // Put the dequeued tree node to Map
        // having key as horizontal distance. Every
        // time we find a node having same horizontal
        // distance we need to replace the data in
        // the map.
        m[hd] = temp->data;
 
        if (temp->left) {
            temp->left->hd = hd - 1;
            q.push(temp->left);
        }
        if (temp->right) {
            temp->right->hd = hd + 1;
            q.push(temp->right);
        }
    }
 
    map<int, int>::iterator itr;
 
    // Sum up all the nodes in bottom view of the tree
    for (itr = m.begin(); itr != m.end(); itr++)
        sum += itr->second;
 
    return sum;
}
 
// Driver Code
int main()
{
    Node* root = newNode(20);
    root->left = newNode(8);
    root->right = newNode(22);
    root->left->left = newNode(5);
    root->left->right = newNode(3);
    root->right->left = newNode(4);
    root->right->right = newNode(25);
    root->left->right->left = newNode(10);
    root->left->right->right = newNode(14);
 
    cout << SumOfBottomView(root);
 
    return 0;
}

Java

// Java implementation of
// the above approach
import java.util.*;
 
class GFG{
     
// Structure of binary tree
public static class Node
{
    public Node left;
    public Node right;
    public int hd;
    public int data;
};
   
// Function to create
// a new node
static Node newNode(int key)
{
    Node node = new Node();
    node.data = key;
    node.left = null;
    node.right = null;
    return node;
}
   
// Function that returns the sum of
// nodes in bottom view of binary tree
static int SumOfBottomView(Node root)
{
    if (root == null)
        return 0;
     
    Queue<Node> q = new LinkedList<>();
     
    HashMap<Integer,
            Integer> m = new HashMap<Integer,
                                     Integer>();
    int hd = 0;
    root.hd = hd;
    int sum = 0;
     
    // Push node and horizontal
    // distance to queue
    q.add(root);
     
    while (q.size() != 0)
    {
        Node temp = q.poll();
        hd = temp.hd;
         
        // Put the dequeued tree node
        // to Map having key as horizontal
        // distance. Every time we find a
        // node having same horizontal distance
        // we need to replace the data in
        // the map.
        m.put(hd, temp.data);
         
        if (temp.left != null)
        {
            temp.left.hd = hd - 1;
            q.add(temp.left);
        }
        if (temp.right != null)
        {
            temp.right.hd = hd + 1;
            q.add(temp.right);
        }
    }   
     
    // Sum up all the nodes in
    // bottom view of the tree   
    for(int value : m.values())
    {
        sum += value;
    }
    return sum;
}
   
// Driver code
public static void main(String[] args)
{
    Node root = newNode(20);
    root.left = newNode(8);
    root.right = newNode(22);
    root.left.left = newNode(5);
    root.left.right = newNode(3);
    root.right.left = newNode(4);
    root.right.right = newNode(25);
    root.left.right.left = newNode(10);
    root.left.right.right = newNode(14);
     
    System.out.println(SumOfBottomView(root));
}
}
 
// This code is contributed by pratham76

Python3

# Python3 implementation of the above approach
 
class Node:
     
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.hd = None
 
# Function that returns the Sum of
# nodes in bottom view of binary tree
def SumOfBottomView(root):
 
    if root == None:
        return 0
     
    q = []
    m = {}
    hd, Sum = 0, 0
    root.hd = hd
 
    # Push node and horizontal
    # distance to queue
    q.append(root)
 
    while len(q) > 0:
        temp = q.pop(0)
        hd = temp.hd
 
        # Put the dequeued tree node to Map
        # having key as horizontal distance.
        # Every time we find a node having
        # same horizontal distance we need
        # to replace the data in the map.
        m[hd] = temp.data
 
        if temp.left != None:
            temp.left.hd = hd - 1
            q.append(temp.left)
         
        if temp.right != None:
            temp.right.hd = hd + 1
            q.append(temp.right)
 
    # Sum up all the nodes in bottom
    # view of the tree
    for itr in m:
        Sum += m[itr]
 
    return Sum
 
# Driver Code
if __name__ == "__main__":
 
    root = Node(20)
    root.left = Node(8)
    root.right = Node(22)
    root.left.left = Node(5)
    root.left.right = Node(3)
    root.right.left = Node(4)
    root.right.right = Node(25)
    root.left.right.left = Node(10)
    root.left.right.right = Node(14)
 
    print(SumOfBottomView(root))
     
# This code is contributed by Rituraj Jain

C#

// C# implementation of
// the above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG
{
// Structure of binary tree
public class Node
{
  public Node left;
  public Node right;
  public int hd;
  public int data;
};
  
// Function to create
// a new node
static Node newNode(int key)
{
  Node node = new Node();
  node.data = key;
  node.left = null;
  node.right = null;
  return node;
}
  
// Function that returns the sum of
// nodes in bottom view of binary tree
static int SumOfBottomView(Node root)
{
  if (root == null)
    return 0;
 
  Queue q = new Queue();
  Dictionary<int,
             int> m = new Dictionary<int,
                                     int>();
  int hd = 0;
  root.hd = hd;
  int sum = 0;
 
  // Push node and horizontal
  // distance to queue
  q.Enqueue(root);
 
  while (q.Count != 0)
  {
    Node temp = (Node)q.Peek();
    q.Dequeue();
    hd = temp.hd;
 
    // Put the dequeued tree node
    // to Map having key as horizontal
    // distance. Every time we find a
    // node having same horizontal distance
    // we need to replace the data in
    // the map.
    m[hd] = temp.data;
 
    if (temp.left != null)
    {
      temp.left.hd = hd - 1;
      q.Enqueue(temp.left);
    }
    if (temp.right != null)
    {
      temp.right.hd = hd + 1;
      q.Enqueue(temp.right);
    }
  }   
   
  // Sum up all the nodes in
  // bottom view of the tree   
  foreach(KeyValuePair<int,
                       int> itr in m)
  {
    sum += itr.Value;
  }
  return sum;
}
  
// Driver code
public static void Main(string[] args)
{
  Node root = newNode(20);
  root.left = newNode(8);
  root.right = newNode(22);
  root.left.left = newNode(5);
  root.left.right = newNode(3);
  root.right.left = newNode(4);
  root.right.right = newNode(25);
  root.left.right.left = newNode(10);
  root.left.right.right = newNode(14);
  Console.Write(SumOfBottomView(root));
}
}
 
// This code is contributed by rutvik_56
Output: 

58

Структуры данных

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Различия между структурой данных массива и словаря
21 Января, 2023
TCS SDE Sheet: Вопросы и ответы для интервью
12 Января, 2023
Множественные сравнения в очереди приоритетов С++?
6 Января, 2023
Когда использовать Queue over ArrayList в Java?
6 Января, 2023
Введение в связанный список — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Введение в массивы — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Как подготовиться к ICFP или Международной конференции по функциональному программированию?
12 Декабря, 2022