Сумма двоюродных братьев данного узла в двоичном дереве

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

Учитывая двоичное дерево и значение данных узла. Задача состоит в том, чтобы найти сумму двоюродных узлов данного узла. Если у данного узла нет кузенов, верните -1.
Примечание: дано, что все узлы имеют разные значения и данный узел существует в дереве.

Примеры:

Вход: 
                1
              / 
             3 7
           /  / 
          6 5 4 13
             / / 
            10 17 15
         ключ = 13
Выход: 11
Двоюродные узлы - 5 и 6, что дает сумму 11. 

Вход:
                1
              / 
             3 7
           /  / 
          6 5 4 13
             / / 
            10 17 15
           ключ = 7
Выход: -1
Нет узлов-родственников узла со значением 7.

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

Подход: подход заключается в обходе дерева в порядке уровней. Выполняя обход порядка уровней, найдите сумму дочерних узлов следующего уровня. Добавьте к сумме значение дочернего узла и проверьте, является ли какой-либо из дочерних узлов целевым узлом или нет. Если да, то не добавляйте к сумме значение ни одного из дочерних элементов. После прохождения текущего уровня, если целевой узел присутствует на следующем уровне, завершите обход порядка уровней, и найденная сумма будет суммой двоюродных узлов.

Below is the implementation of the above approach:

C++

// CPP program to find sum of cousins
// of given node in binary tree.
#include <bits/stdc++.h>
using namespace std;
  
// A Binary Tree Node
struct Node {
    int data;
    struct Node *left, *right;
};
  
// A utility function to create a new
// Binary Tree Node
struct Node* newNode(int item)
{
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->data = item;
    temp->left = temp->right = NULL;
    return temp;
}
  
// Function to find sum of cousins of
// a given node.
int findCousinSum(Node* root, int key)
{
    if (root == NULL)
        return -1;
  
    // Root node has no cousins so return -1.
    if (root->data == key) {
        return -1;
    }
  
    // To store sum of cousins.
    int currSum = 0;
  
    // To store size of current level.
    int size;
  
    // To perform level order traversal.
    queue<Node*> q;
    q.push(root);
  
    // To represent that target node is
    // found.
    bool found = false;
  
    while (!q.empty()) {
  
        // If target node is present at
        // current level, then return
        // sum of cousins stored in currSum.
        if (found == true) {
            return currSum;
        }
  
        // Find size of current level and
        // traverse entire level.
        size = q.size();
        currSum = 0;
  
        while (size) {
            root = q.front();
            q.pop();
  
            // Check if either of the existing
            // children of given node is target
            // node or not. If yes then set
            // found equal to true.
            if ((root->left && root->left->data == key)
                || (root->right && root->right->data == key)) {
                found = true;
            }
  
            // If target node is not children of
            // current node, then its childeren can be cousin
            // of target node, so add their value to sum.
            else {
                if (root->left) {
                    currSum += root->left->data;
                    q.push(root->left);
                }
  
                if (root->right) {
                    currSum += root->right->data;
                    q.push(root->right);
                }
            }
  
            size--;
        }
    }
  
    return -1;
}
  
// Driver Code
int main()
{
    /*
                1
              / 
             3    7
           /    /
          6   5  4  13
             /  /
            10 17 15
    */
  
    struct Node* root = newNode(1);
    root->left = newNode(3);
    root->right = newNode(7);
    root->left->left = newNode(6);
    root->left->right = newNode(5);
    root->left->right->left = newNode(10);
    root->right->left = newNode(4);
    root->right->right = newNode(13);
    root->right->left->left = newNode(17);
    root->right->left->right = newNode(15);
  
    cout << findCousinSum(root, 13) << " ";
  
    cout << findCousinSum(root, 7) << " ";
    return 0;
}

Java

// Java program to find sum of cousins
// of given node in binary tree.
import java.util.*;
class Sol
{
      
// A Binary Tree Node
static class Node 
{
    int data;
    Node left, right;
};
  
// A utility function to create a new
// Binary Tree Node
static Node newNode(int item)
{
    Node temp = new Node();
    temp.data = item;
    temp.left = temp.right = null;
    return temp;
}
  
// Function to find sum of cousins of
// a given node.
static int findCousinSum(Node root, int key)
{
    if (root == null)
        return -1;
  
    // Root node has no cousins so return -1.
    if (root.data == key) 
    {
        return -1;
    }
  
    // To store sum of cousins.
    int currSum = 0;
  
    // To store size of current level.
    int size;
  
    // To perform level order traversal.
    Queue<Node> q=new LinkedList<Node>();
    q.add(root);
  
    // To represent that target node is
    // found.
    boolean found = false;
  
    while (q.size() > 0) 
    {
  
        // If target node is present at
        // current level, then return
        // sum of cousins stored in currSum.
        if (found == true) 
        {
            return currSum;
        }
  
        // Find size of current level and
        // traverse entire level.
        size = q.size();
        currSum = 0;
  
        while (size > 0) 
        {
            root = q.peek();
            q.remove();
  
            // Check if either of the existing
            // children of given node is target
            // node or not. If yes then set
            // found equal to true.
            if ((root.left!=null && root.left.data == key)
                || (root.right!=null && root.right.data == key)) 
            {
                found = true;
            }
  
            // If target node is not children of
            // current node, then its childeren can be cousin
            // of target node, so add their value to sum.
            else 
            {
                if (root.left != null) 
                {
                    currSum += root.left.data;
                    q.add(root.left);
                }
  
                if (root.right != null) 
                {
                    currSum += root.right.data;
                    q.add(root.right);
                }
            }
  
            size--;
        }
    }
  
    return -1;
}
  
// Driver Code
public static void main(String args[])
{
    /*
                1
            /
            3 7
        / /
        6 5 4 13
            / /
            10 17 15
    */
  
    Node root = newNode(1);
    root.left = newNode(3);
    root.right = newNode(7);
    root.left.left = newNode(6);
    root.left.right = newNode(5);
    root.left.right.left = newNode(10);
    root.right.left = newNode(4);
    root.right.right = newNode(13);
    root.right.left.left = newNode(17);
    root.right.left.right = newNode(15);
  
    System.out.print( findCousinSum(root, 13) + " ");
  
    System.out.print( findCousinSum(root, 7) + " ");
}
}
  
// This code is contributed by Arnab Kundu

Python3

""" Python3 program to find sum of cousins 
of given node in binary tree """
  
# A Binary Tree Node 
# Utility function to create a new tree node 
class newNode: 
  
    # Constructor to create a newNode 
    def __init__(self, data): 
        self.data = data 
        self.left = None
        self.right = None
  
# Function to find sum of cousins of 
# a given node. 
def findCousinSum( root, key):
  
    if (root == None): 
        return -1
  
    # Root node has no cousins so return -1. 
    if (root.data == key):
        return -1
      
  
    # To store sum of cousins. 
    currSum = 0
  
    # To store size of current level. 
    size = 0
  
    # To perform level order traversal. 
    q = [] 
    q.append(root) 
  
    # To represent that target node is 
    # found. 
    found = False
  
    while (len(q)): 
  
        # If target node is present at 
        # current level, then return 
        # sum of cousins stored in currSum. 
        if (found == True): 
            return currSum 
          
        # Find size of current level and 
        # traverse entire level. 
        size = len(q)
        currSum = 0
  
        while (size): 
            root = q[0] 
            q.pop(0) 
  
            # Check if either of the existing 
            # children of given node is target 
            # node or not. If yes then set 
            # found equal to true. 
            if ((root.left and root.left.data == key) or 
                (root.right and root.right.data == key)) :
                found = True
              
            # If target node is not children of current 
            # node, then its childeren can be cousin 
            # of target node, so add their value to sum. 
            else:
                if (root.left):
                    currSum += root.left.data 
                    q.append(root.left) 
                  
                if (root.right) :
                    currSum += root.right.data 
                    q.append(root.right) 
  
            size -= 1
    return -1
                          
# Driver Code
if __name__ == "__main__":
  
    """ 
                1 
            /  
            3 7 
        / /  
        6 5 4 13 
            / /  
            10 17 15 
    """
    root = newNode(1) 
    root.left = newNode(3) 
    root.right = newNode(7) 
    root.left.left = newNode(6) 
    root.left.right = newNode(5) 
    ro
Структуры данных

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

Различия между структурой данных массива и словаря
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