Вывести все пути от корня к листу с максимальным количеством четных узлов

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

Для двоичного дерева задача состоит в том, чтобы напечатать все возможные пути от корня к листу, имеющие максимальное количество четных узлов.

Примеры:

Input: 

             2
            / 
           6   3
          /    
         4   7   11
        /    
       10  12   1

Output: 
2 -> 6 -> 4 -> 10 
2 -> 6 -> 4 -> 12 
Explanation: 
Count of even nodes on the path 2 -> 6 -> 4 -> 10 = 4 
Count of even nodes on the path 2 -> 6 -> 4 -> 12 = 4 
Count of even nodes on the path 2 -> 6 -> 7 -> 1 = 2 
Count of even nodes on the path 2 -> 3 -> 11 = 1 
Therefore, the paths consisting of maximum count of even nodes are {2 -> 6 -> 4 -> 10} and {2 -> 6 -> 4 -> 12 }. 

 Input:  

             5
            / 
           6   3
          /    
         4   9   2

Output: 5 -> 6 -> 4. 

Approach: The problem can be solved using Preorder Traversal. The idea is to traverse the given Binary Tree and find the maximum count of even nodes possible in a root-to-leaf path. Finally, traverse the tree and print all possible root-to-leaf paths having the maximum count of even nodes. Follow the steps below to solve the problem:

  • Initialize two variables, say cntMaxEven and cntEven to store the maximum count of even nodes from the root to a leaf node and count of even nodes from root to a leaf node.
  • Traverse the tree and check the following conditions: 
    • Check if current node is a leaf node and cntEven > cntMaxEven or not. If found to be true then update cntMaxEven = cntEven.
    • Otherwise, check if the current node is an even node or not. If found to be true, then Update cntEven += 1.
  • Finally, traverse the tree and print all possible root-to-leaf paths having a count of even nodes equal to cntMaxEven.

C++

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Structure of the binary tree
struct Node {
    // Stores data
    int data;
 
    // Stores left child
    Node* left;
 
    // Stores right child
    Node* right;
 
    // Initialize a node
    // of binary tree
    Node(int val)
    {
 
        // Update data;
        data = val;
        left = right = NULL;
    }
};
 
// Function to find maximum count
// of even nodes in a path
int cntMaxEvenNodes(Node* root)
{
 
    // If the tree is an
    // empty binary tree.
    if (root == NULL) {
        return 0;
    }
 
    // Stores count of even nodes
    // in current subtree
    int cntEven = 0;
 
    // If root node is
    // an even node
    if (root->data % 2
        == 0) {
 
        // Update cntEven
        cntEven += 1;
    }
 
    // Stores count of even nodes
    // in left subtree.
    int X = cntMaxEvenNodes(
        root->left);
 
    // Stores count of even nodes
    // in right subtree.
    int Y = cntMaxEvenNodes(
        root->right);
 
    // cntEven
    cntEven += max(X, Y);
 
    return cntEven;
}
 
// Function to print paths having
// count of even nodes equal
// to maximum count of even nodes
void printPath(Node* root, int cntEven,
               int cntMaxEven,
               vector<int>& path)
{
    // If the tree is an
    // empty Binary Tree
    if (root == NULL) {
        return;
    }
 
    // If current node value is even
    if (root->data % 2 == 0) {
        path.push_back(
            root->data);
        cntEven += 1;
    }
 
    // If current node is
    // a leaf node
    if (root->left == NULL
        && root->right == NULL) {
 
        // If count of even nodes in
        // path is equal to cntMaxEven
        if (cntEven == cntMaxEven) {
 
            // Stores length of path
            int N = path.size();
 
            // Print path
            for (int i = 0; i < N - 1;
                 i++) {
                cout << path[i] << " -> ";
            }
            cout << path[N - 1] << endl;
        }
    }
 
    // Left subtree
    printPath(root->left, cntEven,
              cntMaxEven, path);
 
    // Right subtree
    printPath(root->right, cntEven,
              cntMaxEven, path);
 
    // If current node is even
    if (root->data % 2 == 0) {
        path.pop_back();
 
        // Update cntEven
        cntEven--;
    }
}
 
// Utility Function to print path
// from root to leaf node having
// maximum count of even nodes
void printMaxPath(Node* root)
{
    // Stores maximum count of even
    // nodes of a path in the tree
    int cntMaxEven;
 
    cntMaxEven
        = cntMaxEvenNodes(root);
 
    // Stores path of tree having
    // even nodes
    vector<int> path;
 
    printPath(root, 0, cntMaxEven,
              path);
}
 
// Driver code
int main()
{
    // Create tree.
    Node* root = NULL;
    root = new Node(2);
    root->left = new Node(6);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(7);
    root->right->right = new Node(11);
    root->left->left->left = new Node(10);
    root->left->left->right = new Node(12);
    root->left->right->right = new Node(1);
 
    printMaxPath(root);
}

Java

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
     
// Structure of the binary tree
static class Node
{
     
    // Stores data
    int data;
 
    // Stores left child
    Node left;
 
    // Stores right child
    Node right;
 
    // Initialize a node
    // of binary tree
    Node(int val)
    {
 
        // Update data;
        data = val;
        left = right = null;
    }
};
 
// Function to find maximum count
// of even nodes in a path
static int cntMaxEvenNodes(Node root)
{
     
    // If the tree is an
    // empty binary tree.
    if (root == null)
    {
        return 0;
    }
 
    // Stores count of even nodes
    // in current subtree
    int cntEven = 0;
 
    // If root node is
    // an even node
    if (root.data % 2 == 0)
    {
         
        // Update cntEven
        cntEven += 1;
    }
 
    // Stores count of even nodes
    // in left subtree.
    int X = cntMaxEvenNodes(root.left);
 
    // Stores count of even nodes
    // in right subtree.
    int Y = cntMaxEvenNodes(root.right);
 
    // cntEven
    cntEven += Math.max(X, Y);
 
    return cntEven;
}
 
// Function to print paths having
// count of even nodes equal
// to maximum count of even nodes
static void printPath(Node root, int cntEven,
                      int cntMaxEven,
                      Vector<Integer> path)
{
     
    // If the tree is an
    // empty Binary Tree
    if (root == null)
    {
        return;
    }
 
    // If current node value is even
    if (root.data % 2 == 0)
    {
        path.add(root.data);
        cntEven += 1;
    }
 
    // If current node is
    // a leaf node
    if (root.left == null &&
       root.right == null)
    {
         
        // If count of even nodes in
        // path is equal to cntMaxEven
        if (cntEven == cntMaxEven)
        {
             
            // Stores length of path
            int N = path.size();
 
            // Print path
            for(int i = 0; i < N - 1; i++)
            {
                System.out.print(path.get(i) + " -> ");
            }
            System.out.print(path.get(N - 1) + " ");
        }
    }
 
    // Left subtree
    printPath(root.left, cntEven,
              cntMaxEven, path);
 
    // Right subtree
    printPath(root.right, cntEven,
              cntMaxEven, path);
 
    // If current node is even
    if (root.data % 2 == 0)
    {
        path.remove(path.size() - 1);
 
        // Update cntEven
        cntEven--;
    }
}
 
// Utility Function to print path
// from root to leaf node having
// maximum count of even nodes
static void printMaxPath(Node root)
{
     
    // Stores maximum count of even
    // nodes of a path in the tree
    int cntMaxEven;
 
    cntMaxEven = cntMaxEvenNodes(root);
 
    // Stores path of tree having
    // even nodes
    Vector<Integer> path = new Vector<>();
 
    printPath(root, 0, cntMaxEven,
              path);
}
 
// Driver code
public static void main(String[] args)
{
     
    // Create tree.
    Node root = null;
    root = new Node(2);
    root.left = new Node(6);
    root.right = new Node(3);
    root.left.left = new Node(4);
    root.left.right = new Node(7);
    root.right.right = new Node(11);
    root.left.left.left = new Node(10);
    root.left.left.right = new Node(12);
    root.left.right.right = new Node(1);
 
    printMaxPath(root);
}
}
 
// This code is contributed by Amit Katiyar

Python3

# Python3 program to implement
# the above approach
 
# Structure of the binary tree
class newNode:
     
    def __init__(self, val):
         
        self.data = val
        self.left = None
        self.right = None
 
path = []
 
# Function to find maximum count
# of even nodes in a path
def cntMaxEvenNodes(root):
   
    # If the tree is an
    # empty binary tree.
    if (root == None):
        return 0
 
    # Stores count of even nodes
    # in current subtree
    cntEven = 0
 
    # If root node is
    # an even node
    if (root.data % 2 == 0):
         
        # Update cntEven
        cntEven += 1
 
    # Stores count of even nodes
    # in left subtree.
    X = cntMaxEvenNodes(root.left)
 
    # Stores count of even nodes
    # in right subtree.
    Y = cntMaxEvenNodes(root.right)
 
    # cntEven
    cntEven += max(X, Y)
 
    return cntEven
 
# Function to print paths having
# count of even nodes equal
# to maximum count of even nodes
def printPath(root, cntEven, cntMaxEven):
     
    global path
     
    # If the tree is an
    # empty Binary Tree
    if (root == None):
        return
 
    # If current node value is even
    if (root.data % 2 == 0):
        path.append(root.data)
        cntEven += 1
 
    # If current node is
    # a leaf node
    if (root.left == None and
       root.right == None):
         
        # If count of even nodes in
        # path is equal to cntMaxEven
        if (cntEven == cntMaxEven):
             
            # Stores length of path
            N = len(path)
 
            # Print path
            for i in range(N - 1):
                print(path[i], end = "->")
                 
            print(path[N
Структуры данных

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

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