Рубрики

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

Для заданного двоичного дерева задача состоит в том, чтобы найти сумму узлов, которые видны в левом представлении. Вид слева двоичного дерева — это набор узлов, видимых при просмотре дерева слева.

Примеры:

Input:
       1
      /  \
     2    3
    / \    \
   4   5    6
Output: 7
1 + 2 + 4 = 7

Input:
       1
      /  \
    2      3
      \   
        4  
          \
            5
             \
               6
Output: 18

Подход: проблема может быть решена с помощью простого рекурсивного обхода. Мы можем отслеживать уровень узла, передавая параметр всем рекурсивным вызовам. Идея состоит в том, чтобы также отслеживать максимальный уровень и обходить дерево таким образом, чтобы левое поддерево посещалось перед правым поддеревом. Всякий раз, когда встречается узел, уровень которого превышает максимальный уровень, добавьте значение узла к сумме, поскольку он является первым узлом на своем уровне (обратите внимание, что левое поддерево проходит перед правым поддеревом).

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  

class Node {

public:

    int data;

    Node *left, *right;

};

  
// Полезная функция для создания
// новый узел двоичного дерева

Node* newNode(int item)

{

    Node* temp = new Node();

    temp->data = item;

    temp->left = temp->right = NULL;

    return temp;

}

  
// Рекурсивная функция для нахождения суммы узлов
// левого обзора данного бинарного дерева

void sumLeftViewUtil(Node* root, int level, int* max_level, int* sum)

{

    // Базовый вариант

    if (root == NULL)

        return;

  

    // Если это первый узел его уровня

    if (*max_level < level) {

        *sum += root->data;

        *max_level = level;

    }

  

    // Повтор для левого и правого поддеревьев

    sumLeftViewUtil(root->left, level + 1, max_level, sum);

    sumLeftViewUtil(root->right, level + 1, max_level, sum);

}

  
// Обертка над sumLeftViewUtil ()

void sumLeftView(Node* root)

{

    int max_level = 0;

    int sum = 0;

    sumLeftViewUtil(root, 1, &max_level, &sum);

    cout << sum;

}

  
// Код драйвера

int main()

{

    Node* root = newNode(12);

    root->left = newNode(10);

    root->right = newNode(30);

    root->right->left = newNode(25);

    root->right->right = newNode(40);

  

    sumLeftView(root);

  

    return 0;

}

Джава

// Java реализация подхода

  
// Класс для узла дерева

class Node {

    int data;

    Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  

class BinaryTree {

    Node root;

    static int max_level = 0;

    static int sum = 0;

  

    // Рекурсивная функция для нахождения суммы узлов

    // левого обзора данного бинарного дерева

    void sumLeftViewUtil(Node node, int level)

    {

        // Базовый вариант

        if (node == null)

            return;

  

        // Если это первый узел его уровня

        if (max_level < level) {

            sum += node.data;

            max_level = level;

        }

  

        // Повтор для левого и правого поддеревьев

        sumLeftViewUtil(node.left, level + 1);

        sumLeftViewUtil(node.right, level + 1);

    }

  

    // Обертка над sumLeftViewUtil ()

    void sumLeftView()

    {

  

        sumLeftViewUtil(root, 1);

        System.out.print(sum);

    }

  

    // Код драйвера

    public static void main(String args[])

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(12);

        tree.root.left = new Node(10);

        tree.root.right = new Node(30);

        tree.root.right.left = new Node(25);

        tree.root.right.right = new Node(40);

  

        tree.sumLeftView();

    }

}

python3

# Python3 реализация подхода

  
# Узел двоичного дерева

class Node: 

  

    # Конструктор для создания нового узла

    def __init__(self, data): 

        self.data = data 

        self.left = None

        self.right = None

  

  
# Рекурсивная функция для нахождения суммы узлов
# левого представления данного двоичного дерева

def sumLeftViewUtil(root, level, max_level, sum): 

      

    # Базовый вариант

    if root is None

        return

  

    # Если это первый узел своего уровня

    if (max_level[0] < level): 

        sum[0]+= root.data 

        max_level[0] = level 

  

    # Повтор для левого и правого поддерева

    sumLeftViewUtil(root.left, level + 1, max_level, sum

    sumLeftViewUtil(root.right, level + 1, max_level, sum

  

  
# Обертка над sumLeftViewUtil ()

def sumLeftView(root): 

    max_level = [0

    sum =[0]

    sumLeftViewUtil(root, 1, max_level, sum

    print(sum[0])

  

  
# Код драйвера

root = Node(12

root.left = Node(10

root.right = Node(20

root.right.left = Node(25

root.right.right = Node(40

sumLeftView(root)

C #

// C # реализация подхода

using System;

  
// Класс для узла дерева

public class Node {

    public int data;

    public Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  

public class BinaryTree {

    public Node root;

    public static int max_level = 0;

    public static int sum = 0;

  

    // Рекурсивная функция для нахождения суммы узлов

    // левого обзора данного бинарного дерева

    public virtual void leftViewUtil(Node node, int level)

    {

        // Базовый вариант

        if (node == null) {

            return;

        }

  

        // Если это первый узел его уровня

        if (max_level < level) {

            sum += node.data;

            max_level = level;

        }

  

        // Повтор для левого и правого поддеревьев

        leftViewUtil(node.left, level + 1);

        leftViewUtil(node.right, level + 1);

    }

  

    // Обёртка над leftViewUtil ()

    public virtual void leftView()

    {

        leftViewUtil(root, 1);

        Console.Write(sum);

    }

  

    // Код драйвера

    public static void Main(string[] args)

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(12);

        tree.root.left = new Node(10);

        tree.root.right = new Node(30);

        tree.root.right.left = new Node(25);

        tree.root.right.right = new Node(40);

  

        tree.leftView();

    }

}

Выход:

47

Рекомендуемые посты:

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

0.00 (0%) 0 votes