Рубрики

Найти сумму всех левых листьев в данном бинарном дереве

По заданному бинарному дереву найдите в нем сумму всех оставленных листьев. Например, сумма всех левых листьев в нижнем двоичном дереве равна 5 + 1 = 6.

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

Ниже приводится реализация вышеуказанной идеи.

C ++

// Программа на C ++ для нахождения суммы всех левых листьев
#include <iostream>

using namespace std;

  
/ * Узел двоичного дерева имеет ключ, указатель влево и вправо

   дети */

struct Node

{

    int key;

    struct Node* left, *right;

};

  
/ * Вспомогательная функция, которая выделяет новый узел с

   заданные данные и NULL левый и правый указатель. * /

Node *newNode(char k)

{

    Node *node = new Node;

    node->key = k;

    node->right = node->left = NULL;

    return node;

}

  
// Утилита для проверки, является ли данный узел листовым или нет

bool isLeaf(Node *node)

{

   if (node == NULL)

       return false;

   if (node->left == NULL && node->right == NULL)

       return true;

   return false;

}

  
// Эта функция возвращает сумму всех левых листьев в данном
// двоичное дерево

int leftLeavesSum(Node *root)

{

    // Инициализировать результат

    int res = 0;

  

    // Обновить результат, если root не равен NULL

    if (root != NULL)

    {

       // Если слева от корня NULL, то добавить ключ

       // левый ребенок

       if (isLeaf(root->left))

            res += root->left->key;

       else // Остальное recur для левого потомка root

            res += leftLeavesSum(root->left);

  

       // Повторяем для правого потомка root и обновляем res

       res += leftLeavesSum(root->right);

    }

  

    // вернуть результат

    return res;

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

    // Давайте построим двоичное дерево

    struct Node *root         = newNode(20);

    root->left                = newNode(9);

    root->right               = newNode(49);

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

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

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

    root->left->left          = newNode(5);

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

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

    cout << "Sum of left leaves is "

         << leftLeavesSum(root);

    return 0;

}

Джава

// Java программа для поиска суммы всех левых листьев

class Node 

{

    int data;

    Node left, right;

   

    Node(int item) 

    {

        data = item;

        left = right = null;

    }

}

   

class BinaryTree 

{

    Node root;

   

    // Утилита для проверки, является ли данный узел листовым или нет

    boolean isLeaf(Node node) 

    {

        if (node == null)

            return false;

        if (node.left == null && node.right == null)

            return true;

        return false;

    }

   

     // Эта функция возвращает сумму всех левых листьев в данном

     // двоичное дерево

    int leftLeavesSum(Node node) 

    {

        // Инициализировать результат

        int res = 0;

   

        // Обновить результат, если root не равен NULL

        if (node != null

        {

            // Если слева от корня NULL, то добавить ключ

            // левый ребенок

            if (isLeaf(node.left))

                res += node.left.data;

            else // Остальное recur для левого потомка root

                res += leftLeavesSum(node.left);

   

            // Повторяем для правого потомка root и обновляем res

            res += leftLeavesSum(node.right);

        }

   

        // вернуть результат

        return res;

    }

   

    // Драйвер программы

    public static void main(String args[]) 

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(20);

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

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

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

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

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

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

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

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

   

        System.out.println("The sum of leaves is "

                                       tree.leftLeavesSum(tree.root));

    }

}

   
// Этот код предоставлен Mayank Jaiswal

питон

# Программа Python, чтобы найти сумму всех оставленных листьев

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

class Node:

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

    def __init__(self, key):

        self.key = key

        self.left = None

        self.right = None

  
# Сервисная функция, чтобы проверить, является ли данный узел листом или нет

def isLeaf(node):

    if node is None:

        return False

    if node.left is None and node.right is None:

        return True

    return False

  
# Эта функция возвращает сумму всех левых листьев в
# данное двоичное дерево

def leftLeavesSum(root):

  

    # Инициализировать результат

    res = 0

      

    # Обновить результат, если root не None

    if root is not None:

  

        # Если слева от корня None, то добавьте ключ

        # левый ребенок

        if isLeaf(root.left):

            res += root.left.key

        else:

            # Остальное повторяется для левого потомка root

            res += leftLeavesSum(root.left)

  

        # Повторить для правого потомка root и обновить res

        res += leftLeavesSum(root.right)

    return res

  
# Программа драйвера для проверки вышеуказанной функции

  
# Давайте ограничимся двоичным деревом, показанным в функции выше

root = Node(20)

root.left = Node(9)

root.right = Node(49)

root.right.left = Node(23)        

root.right.right = Node(52)

root.right.right.left = Node(50)

root.left.left = Node(5)

root.left.right = Node(12)

root.left.right.right = Node(12)

print "Sum of left leaves is", leftLeavesSum(root)

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

using System;

  
// C # программа для поиска суммы всех левых листьев

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 virtual bool isLeaf(Node node)

    {

        if (node == null)

        {

            return false;

        }

        if (node.left == null && node.right == null)

        {

            return true;

        }

        return false;

    }

  

     // Эта функция возвращает сумму всех левых листьев в данном

     // двоичное дерево

    public virtual int leftLeavesSum(Node node)

    {

        // Инициализировать результат

        int res = 0;

  

        // Обновить результат, если root не равен NULL

        if (node != null)

        {

            // Если слева от корня NULL, то добавить ключ

            // левый ребенок

            if (isLeaf(node.left))

            {

                res += node.left.data;

            }

            else // Остальное recur для левого потомка root

            {

                res += leftLeavesSum(node.left);

            }

  

            // Повторяем для правого потомка root и обновляем res

            res += leftLeavesSum(node.right);

        }

  

        // вернуть результат

        return res;

    }

  

    // Драйвер программы

    public static void Main(string[] args)

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(20);

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

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

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

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

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

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

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

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

  

        Console.WriteLine("The sum of leaves is " + tree.leftLeavesSum(tree.root));

    }

}

  

  // Этот код предоставлен Shrikant13


Выход:

Sum of left leaves is 78

Временная сложность вышеуказанного решения составляет O (n), где n — количество узлов в двоичном дереве.

Ниже приведен еще один способ решения вышеуказанной проблемы. Это решение переходит в переменную суммы в качестве аккумулятора. Когда встречается левый лист, данные листа складываются в сумму. Временная сложность этого метода также O (n). Спасибо Синь Тонгу (geeksforgeeks userid trent.tong) за предложение этого метода.

C ++

// Программа на C ++ для нахождения суммы всех левых листьев
#include <iostream>

using namespace std;

  
/ * Узел двоичного дерева имеет ключ, указатель влево и вправо

   дети */

struct Node

{

    int key;

    struct Node* left, *right;

};

  
/ * Вспомогательная функция, которая выделяет новый узел с

   заданные данные и NULL левый и правый указатель. * /

Node *newNode(char k)

{

    Node *node = new Node;

    node->key = k;

    node->right = node->left = NULL;

    return node;

}

  
/ * Передать переменную суммы в качестве аккумулятора * /

void leftLeavesSumRec(Node *root, bool isleft, int *sum)

{

    if (!root) return;

  

    // Проверяем, является ли этот узел листовым и оставлен ли он.

    if (!root->left && !root->right && isleft)

        *sum += root->key;

  

    // Передаем 1 слева и 0 справа

    leftLeavesSumRec(root->left,  1, sum);

    leftLeavesSumRec(root->right, 0, sum);

}

  
// Обёртка над рекурсивной функцией

int leftLeavesSum(Node *root)

{

    int sum = 0; // Инициализировать результат

  

    // использовать вышеуказанную рекурсивную функцию для вычисления суммы

    leftLeavesSumRec(root, 0, &sum);

  

    return sum;

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

    // Давайте построим двоичное дерево, показанное в

    // над рисунком

    int sum = 0;

    struct Node *root         = newNode(20);

    root->left                = newNode(9);

    root->right               = newNode(49);

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

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

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

    root->left->left          = newNode(5);

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

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

  

    cout << "Sum of left leaves is " << leftLeavesSum(root) << endl;

    return 0;

}

Джава

// Java программа для поиска суммы всех левых листьев

class Node 

{

    int data;

    Node left, right;

   

    Node(int item) {

        data = item;

        left = right = null;

    }

}

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

class Sum 

{

    int sum = 0;

}

   

class BinaryTree 

{

    Node root;

   

    / * Передать переменную суммы в качестве аккумулятора * /

    void leftLeavesSumRec(Node node, boolean isleft, Sum summ) 

    {

        if (node == null)

            return;

   

        // Проверяем, является ли этот узел листовым и оставлен ли он.

        if (node.left == null && node.right == null && isleft)

            summ.sum = summ.sum + node.data;

   

        // Передаем true для левого и false для правого

        leftLeavesSumRec(node.left, true, summ);

        leftLeavesSumRec(node.right, false, summ);

    }

   

    // Обёртка над рекурсивной функцией

    int leftLeavesSum(Node node) 

    {

        Sum suum = new Sum();

          

        // использовать вышеуказанную рекурсивную функцию для вычисления суммы

        leftLeavesSumRec(node, false, suum);

   

        return suum.sum;

    }

   

    // Драйвер программы

    public static void main(String args[]) 

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(20);

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

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

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

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

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

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

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

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

   

        System.out.println("The sum of leaves is "

                                    tree.leftLeavesSum(tree.root));

    }

}

   
// Этот код предоставлен Mayank Jaiswal

питон

# Программа Python, чтобы найти сумму всех оставленных листьев

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

class Node:

  

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

    def __init__(self, key):

        self.key = key

        self.left = None

        self.right = None

  

def leftLeavesSumRec(root, isLeft, summ):

    if root is None:

        return

      

    # Проверьте, является ли этот узел листовым и оставлен ли

    if root.left is None and root.right is None and isLeft == True:

        summ[0] += root.key

  

    # Пропустить 1 слева и 0 справа

    leftLeavesSumRec(root.left, 1, summ)

    leftLeavesSumRec(root.right, 0, summ)

      

  
# Обёртка над рекурсивной функцией

def leftLeavesSum(root):

    summ = [0] # инициализировать результат

      

    # Используйте вышеуказанную рекурсивную функцию для оценки суммы

    leftLeavesSumRec(root, 0, summ)

      

    return summ[0]

  
# Программа драйвера для проверки вышеуказанной функции

  
# Давайте построим двоичное дерево, показанное в
№ над цифрой

root = Node(20);

root.left= Node(9);

root.right   = Node(49);

root.right.left = Node(23);

root.right.right= Node(52);

root.right.right.left  = Node(50);

root.left.left  = Node(5);

root.left.right = Node(12);

root.left.right.right  = Node(12);

  

print "Sum of left leaves is", leftLeavesSum(root)  

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

using System;

  
// C # программа для поиска суммы всех левых листьев

public class Node

{

    public int data;

    public Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

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

public class Sum

{

    public int sum = 0;

}

  

public class BinaryTree

{

    public Node root;

  

    / * Передать переменную суммы в качестве аккумулятора * /

    public virtual void leftLeavesSumRec(Node node, bool isleft, Sum summ)

    {

        if (node == null)

        {

            return;

        }

  

        // Проверяем, является ли этот узел листовым и оставлен ли он.

        if (node.left == null && node.right == null && isleft)

        {

            summ.sum = summ.sum + node.data;

        }

  

        // Передаем true для левого и false для правого

        leftLeavesSumRec(node.left, true, summ);

        leftLeavesSumRec(node.right, false, summ);

    }

  

    // Обёртка над рекурсивной функцией

    public virtual int leftLeavesSum(Node node)

    {

        Sum suum = new Sum();

  

        // использовать вышеуказанную рекурсивную функцию для вычисления суммы

        leftLeavesSumRec(node, false, suum);

  

        return suum.sum;

    }

  

    // Драйвер программы

    public static void Main(string[] args)

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(20);

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

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

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

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

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

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

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

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

  

        Console.WriteLine("The sum of leaves is " + tree.leftLeavesSum(tree.root));

    }

}

  

  // Этот код предоставлен Shrikant13


Выход:

Sum of left leaves is 78

Итеративный подход:
Это итеративный способ найти сумму левых листьев.
Идея состоит в том, чтобы выполнить обход в глубину на дереве (или Inorder, Preorder или Postorder), используя стек и проверяя, является ли Left Child узлом Leaf. Если это так, то добавьте значение узлов в переменную суммы

# Программа Python, чтобы найти сумму всех оставленных листьев

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

class Node:

  

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

    def __init__(self, key):

        self.key = key

        self.left = None

        self.right = None

  

  
# Вернуть сумму узлов левого листа

def sumOfLeftLeaves(root):

    if(root is None):

        return

      

    # Использование стека для глубинного обхода дерева

    stack = []   

    stack.append(root)

      

    # sum содержит сумму всех левых листьев

    sum = 0

  

    while len(stack) > 0:

        currentNode = stack.pop()

  

        if currentNode.left is not None:

            stack.append(currentNode.left)

              

            # Проверка, является ли левый дочерний узел currentNode конечным узлом

            if currentNode.left.left is None and currentNode.left.right is None:

  

                # если currentNode - это лист, добавить его данные в сумму

                sum = sum + currentNode.left.data 

  

        if currentNode.right is not None:

            stack.append(currentNode.right)

    return sum

  
Код водителя

root = Tree(20);

root.left= Tree(9);

root.right   = Tree(49);

root.right.left = Tree(23);

root.right.right= Tree(52);

root.right.right.left  = Tree(50);

root.left.left  = Tree(5);

root.left.right = Tree(12);

root.left.right.right  = Tree(12);

  

print('Sum of left leaves is {}'.format(sumOfLeftLeaves(root)))

Выход:

Sum of left leaves is 78

Спасибо Шубхам Тамбере за предложенный подход.

Эта статья предоставлена Манишем . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

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

Найти сумму всех левых листьев в данном бинарном дереве

0.00 (0%) 0 votes