Minimice los cambios para convertirlos en un árbol con raíz 1, hijos pares a la izquierda e hijos impares a la derecha

Dado un árbol binario , la tarea es convertir este árbol utilizando un número mínimo de operaciones de incremento-decremento en un árbol que satisfaga las siguientes condiciones:

• El Node raíz siempre es 1.
• Cada hijo izquierdo de un Node es par.
• Todo hijo derecho de un Node es impar. 

Devuelve e imprime el número mínimo de operaciones de incremento-decremento requeridas al final. 

Ejemplos:

Aporte: 

 

Salida: 3
Explicación: 
Dado que la raíz ya es 1, no se necesita ningún cambio en la raíz
El hijo izquierdo del Node raíz es 2, por lo que no se necesita ningún cambio aquí.
El hijo derecho del Node raíz es 2, así que cámbielo a 3, haciendo un cambio de 1.
El hijo izquierdo del Node 2 es 5, así que cámbielo a 4, haciendo un cambio de 1.
El hijo izquierdo del Node 3 es 6, entonces no aquí se necesita un cambio.
El hijo derecho del Node 3 es 8, así que cámbielo a 9, haciendo un cambio de 1.
Por lo tanto, el total de cambios necesarios es 3.

 

Aporte:

 

Salida: 0
Explicación: El árbol dado ya satisface las condiciones dadas.

Enfoque: La idea es cambiar cada Node que no cumpla la condición según la siguiente observación:

• Si el Node raíz no es 1, podemos seguir decrementándolo en 1 hasta que se convierta en 1. Por lo tanto , aquí se necesitan operaciones raíz-1 .
• Si el Node actual es un hijo izquierdo y es impar, simplemente podemos hacerlo par aumentando o disminuyendo en 1. Por lo tanto, aquí se necesita 1 operación .
• Si el Node actual es un hijo derecho y es par, simplemente podemos hacerlo impar incrementando o decrementando en 1. Por lo tanto, aquí se necesita 1 operación .

Por lo tanto, simplemente atraviese el Árbol dado y:

• Agregue operaciones raíz-1 a la respuesta si la raíz no es 1.
• Agregue el conteo de hijos izquierdos que son impares a la respuesta
• También agregue la cantidad de hijos correctos que son pares a la respuesta.

Según la idea anterior, podemos hacer un recorrido DFS según los pasos a continuación:

• Atraviesa a los niños izquierdo y derecho recursivamente.
  • Compruebe si el valor izquierdo del Node visitado no es nulo y si el valor secundario izquierdo del Node es impar
    • Incrementar la respuesta en 1
  • Compruebe si el valor correcto del Node visitado no es nulo y si el valor secundario derecho del Node es par 
    • Incrementar la respuesta en 1
• De nuevo recursivamente llame al Node izquierdo y derecho hasta que se atraviese todo el árbol.
• También verifique si la raíz no es igual a 1. 
  • Si es verdadero, agregue root_value – 1 a la respuesta.
• Devuelve la respuesta al final.

A continuación se muestra la implementación del enfoque anterior:

// C++ code for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// To store the final changes needed
int count_of_changes;
 
struct Node {
    int value;
    struct Node *left, *right;
};
 
// Utility function to create new
// tree node
Node* newNode(int data)
{
    Node* temp = new Node;
    temp->value = data;
    temp->left = temp->right = NULL;
    return temp;
}
 
// DFS function to convert
// binary tree to proper tree
void dfs(Node* root)
{
 
    // Check if given root is NULL
    // base case
    if (root == NULL)
        return;
 
    // Check if visited node's
    // left value is not null and
    // node's left child value is odd
    // decrement its value by 1
    if (root->left
        && root->left->value % 2 == 1) {
        root->left->value -= 1;
        count_of_changes++;
    }
 
    // Check if visited node's
    // value is not null and node's
    // right child value is even,
    // increment its value by 1
    if (root->right
        && root->right->value % 2 == 0) {
        root->right->value += 1;
        count_of_changes++;
    }
 
    // Recursive call for left node
    dfs(root->left);
 
    // Recursive call for right node
    dfs(root->right);
}
 
// Function to find
// the min changes needed
int minCount(Node* root)
{
 
    // Initial value for
    // final changes needed
    count_of_changes = 0;
 
    // Base case to check
    // if root is NULL
    if (root == NULL)
        return count_of_changes;
 
    if (root->value != 1) {
 
        // Add root_value - 1 to the ans
        count_of_changes += root->value - 1;
 
        // Set root->Value to 1
        root->value = 1;
    }
 
    // DFS Function call
    dfs(root);
 
    // Return the final count
    return count_of_changes;
}
 
// Driver Code
int main()
{
 
    // Taking input
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(2);
    root->left->left = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(8);
 
    // Function call
    cout << minCount(root) << endl;
 
    return 0;
}

// JAVA code for the above approach
import java.util.*;
class GFG
{
 
  // To store the final changes needed
  static int count_of_changes;
 
  public static class Node {
    int value;
    Node left, right;
  }
 
  // Utility function to create new
  // tree node
 
  public static Node newNode(int data)
  {
    Node temp = new Node();
    temp.value = data;
    temp.left = temp.right = null;
    return temp;
  }
  // DFS function to convert
  // binary tree to proper tree
  public static void dfs(Node root)
  {
 
    // Check if given root is null
    // base case
    if (root == null)
      return;
 
    // Check if visited node's
    // left value is not null and
    // node's left child value is odd
    // decrement its value by 1
    if (root.left != null && root.left.value % 2 == 1) {
      root.left.value -= 1;
      count_of_changes++;
    }
 
    // Check if visited node's
    // value is not null and node's
    // right child value is even,
    // increment its value by 1
    if (root.right != null && root.right.value % 2 == 0) {
      root.right.value += 1;
      count_of_changes++;
    }
 
    // Recursive call for left node
    dfs(root.left);
 
    // Recursive call for right node
    dfs(root.right);
  }
 
  // Function to find
  // the min changes needed
  public static int minCount(Node root)
  {
 
    // Initial value for
    // final changes needed
    count_of_changes = 0;
 
    // Base case to check
    // if root is null
    if (root == null)
      return count_of_changes;
 
    if (root.value != 1) {
 
      // Add root_value - 1 to the ans
      count_of_changes += root.value - 1;
 
      // Set root->Value to 1
      root.value = 1;
    }
 
    // DFS Function call
    dfs(root);
 
    // Return the final count
    return count_of_changes;
  } 
 
 
  // Driver code
  public static void main(String[] args)
  {
    // Taking input
    Node root = newNode(1);
    root.left = newNode(2);
    root.right = newNode(2);
    root.left.left = newNode(5);
    root.right.left = newNode(6);
    root.right.right = newNode(8);
 
    // Function call
    System.out.println(minCount(root));
 
  }
}
 
// This code is contributed by jana_sayantan.

# Python code for the above approach
 
# To store the final changes needed
count_of_changes = 0
 
class Node:
    def __init__(self,data = 0,left = None,right = None):
        self.data = data
        self.left = left
        self.right = right
 
# Utility function to create new
# tree node
def newNode(data):
 
    temp = Node()
    temp.value = data
    temp.left = temp.right = None
    return temp
 
 
# DFS function to convert
# binary tree to proper tree
def dfs(root):
 
    global count_of_changes
 
    # Check if given root is None
    # base case
    if (root == None):
        return
 
    # Check if visited node's
    # left value is not None and
    # node's left child value is odd
    # decrement its value by 1
    if (root.left and root.left.value % 2 == 1) :
        root.left.value -= 1
        count_of_changes += 1
 
    # Check if visited node's
    # value is not None and node's
    # right child value is even,
    # increment its value by 1
    if (root.right
        and root.right.value % 2 == 0):
        root.right.value += 1
        count_of_changes += 1
 
    # Recursive call for left node
    dfs(root.left)
 
    # Recursive call for right node
    dfs(root.right)
 
# Function to find
# the min changes needed
def minCount(root):
 
    # Initial value for
    # final changes needed
    global count_of_changes
    count_of_changes = 0
 
    # Base case to check
    # if root is None
    if (root == None):
        return count_of_changes
 
    if (root.value != 1):
 
        # Add root_value - 1 to the ans
        count_of_changes += root.value - 1
 
        # Set root.Value to 1
        root.value = 1
 
    # DFS Function call
    dfs(root)
 
    # Return the final count
    return count_of_changes
 
# Driver Code
 
# Taking input
root = newNode(1)
root.left = newNode(2)
root.right = newNode(2)
root.left.left = newNode(5)
root.right.left = newNode(6)
root.right.right = newNode(8)
 
# Function call
print(minCount(root))
 
# This code is contributed by shinjanpatra

// C# program to implement above approach
using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG
{
 
  // To store the final changes needed
  static int count_of_changes;
 
  public class Node {
    public int value;
    public Node left, right;
  }
 
  // Utility function to create new
  // tree node
 
  public static Node newNode(int data)
  {
    Node temp = new Node();
    temp.value = data;
    temp.left = temp.right = null;
    return temp;
  }
 
  // DFS function to convert
  // binary tree to proper tree
  public static void dfs(Node root)
  {
 
    // Check if given root is null
    // base case
    if (root == null)
      return;
 
    // Check if visited node's
    // left value is not null and
    // node's left child value is odd
    // decrement its value by 1
    if (root.left != null && root.left.value % 2 == 1) {
      root.left.value-=1;
      count_of_changes++;
    }
 
    // Check if visited node's
    // value is not null and node's
    // right child value is even,
    // increment its value by 1
    if (root.right != null && root.right.value % 2 == 0) {
      root.right.value += 1;
      count_of_changes++;
    }
 
    // Recursive call for left node
    dfs(root.left);
 
    // Recursive call for right node
    dfs(root.right);
  }
 
  // Function to find
  // the min changes needed
  public static int minCount(Node root)
  {
 
    // Initial value for
    // final changes needed
    count_of_changes = 0;
 
    // Base case to check
    // if root is null
    if (root == null)
      return count_of_changes;
 
    if (root.value != 1) {
 
      // Add root_value - 1 to the ans
      count_of_changes += root.value - 1;
 
      // Set root->Value to 1
      root.value = 1;
    }
 
    // DFS Function call
    dfs(root);
 
    // Return the final count
    return count_of_changes;
  }
 
 
  public static void Main(string[] args){
 
    // Taking input
    Node root = newNode(1);
    root.left = newNode(2);
    root.right = newNode(2);
    root.left.left = newNode(5);
    root.right.left = newNode(6);
    root.right.right = newNode(8);
 
    // Function call
    Console.WriteLine(minCount(root));
 
  }
}
 
// This code is contributed by entertain2022.

<script>
 
// JavaScript code to implement the above approach
 
// To store the final changes needed
let count_of_changes = 0
 
class Node{
    constructor(data = 0,left = null,right = null){
        this.data = data
        this.left = left
        this.right = right
    }   
}
 
// Utility function to create new
// tree node
function newNode(data){
 
    let temp = new Node()
    temp.value = data
    temp.left = temp.right = null
    return temp
}
 
// DFS function to convert
// binary tree to proper tree
function dfs(root){
 
    // Check if given root is null
    // base case
    if (root == null)
        return
 
    // Check if visited node's
    // left value is not null and
    // node's left child value is odd
    // decrement its value by 1
    if (root.left && root.left.value % 2 == 1){
        root.left.value -= 1
        count_of_changes += 1
    }
 
    // Check if visited node's
    // value is not null and node's
    // right child value is even,
    // increment its value by 1
    if (root.right
        && root.right.value % 2 == 0){
        root.right.value += 1
        count_of_changes += 1
    }
 
    // Recursive call for left node
    dfs(root.left)
 
    // Recursive call for right node
    dfs(root.right)
}
 
// Function to find
// the min changes needed
function minCount(root){
 
    // Initial value for
    // final changes needed
    count_of_changes = 0
 
    // Base case to check
    // if root is null
    if (root == null)
        return count_of_changes
 
    if (root.value != 1){
 
        // Add root_value - 1 to the ans
        count_of_changes += root.value - 1
 
        // Set root.Value to 1
        root.value = 1
    }
 
    // DFS Function call
    dfs(root)
 
    // Return the final count
    return count_of_changes
}
 
// Driver Code
 
// Taking input
let root = newNode(1)
root.left = newNode(2)
root.right = newNode(2)
root.left.left = newNode(5)
root.right.left = newNode(6)
root.right.right = newNode(8)
 
// Function call
document.write(minCount(root),"</br>")
 
// This code is contributed by shinjanpatra
 
</script>

3

Complejidad de tiempo: O(V), donde V es el recuento de vértices en el
espacio auxiliar del árbol dado: O(H), que es el tamaño de la pila para las llamadas a funciones, donde H es la altura del árbol.