Dado un árbol binario que tiene elementos pares e impares, hundir todos sus Nodes con valores impares de modo que ningún Node con valor impar pueda ser padre de Node con valor par. Puede haber múltiples salidas para un árbol dado, necesitamos imprimir una de ellas. Siempre es posible convertir un árbol (Tenga en cuenta que un Node con Nodes pares y todos los Nodes impares sigue la regla)
Input :
1
/ \
2 3
Output
2 2
/ \ OR / \
1 3 3 1
Input :
1
/ \
5 8
/ \ / \
2 4 9 10
Output :
2 4
/ \ / \
4 8 OR 2 8 OR .. (any tree with
/ \ / \ / \ / \ same keys and
5 1 9 10 5 1 9 10 no odd is parent
of even)
Le recomendamos encarecidamente que minimice su navegador y que pruebe esto usted mismo primero.
C++
// Program to sink odd nodes to the bottom of
// binary tree
#include<bits/stdc++.h>
using namespace std;
// A binary tree node
struct Node
{
int data;
Node* left, *right;
};
// Helper function to allocates a new node
Node* newnode(int data)
{
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return node;
}
// Helper function to check if node is leaf node
bool isLeaf(Node *root)
{
return (root->left == NULL && root->right == NULL);
}
// A recursive method to sink a tree with odd root
// This method assumes that the subtrees are already
// sinked. This method is similar to Heapify of
// Heap-Sort
void sink(Node *&root)
{
// If NULL or is a leaf, do nothing
if (root == NULL || isLeaf(root))
return;
// if left subtree exists and left child is even
if (root->left && !(root->left->data & 1))
{
// swap root's data with left child and
// fix left subtree
swap(root->data, root->left->data);
sink(root->left);
}
// if right subtree exists and right child is even
else if(root->right && !(root->right->data & 1))
{
// swap root's data with right child and
// fix right subtree
swap(root->data, root->right->data);
sink(root->right);
}
}
// Function to sink all odd nodes to the bottom of binary
// tree. It does a postorder traversal and calls sink()
// if any odd node is found
void sinkOddNodes(Node* &root)
{
// If NULL or is a leaf, do nothing
if (root == NULL || isLeaf(root))
return;
// Process left and right subtrees before this node
sinkOddNodes(root->left);
sinkOddNodes(root->right);
// If root is odd, sink it
if (root->data & 1)
sink(root);
}
// Helper function to do Level Order Traversal of
// Binary Tree level by level. This function is used
// here only for showing modified tree.
void printLevelOrder(Node* root)
{
queue<Node*> q;
q.push(root);
// Do Level order traversal
while (!q.empty())
{
int nodeCount = q.size();
// Print one level at a time
while (nodeCount)
{
Node *node = q.front();
printf("%d ", node->data);
q.pop();
if (node->left != NULL)
q.push(node->left);
if (node->right != NULL)
q.push(node->right);
nodeCount--;
}
// Line separator for levels
printf("\n");
}
}
// Driver program to test above functions
int main()
{
/* Constructed binary tree is
1
/ \
5 8
/ \ / \
2 4 9 10 */
Node *root = newnode(1);
root->left = newnode(5);
root->right = newnode(8);
root->left->left = newnode(2);
root->left->right = newnode(4);
root->right->left = newnode(9);
root->right->right = newnode(10);
sinkOddNodes(root);
printf("Level order traversal of modified tree\n");
printLevelOrder(root);
return 0;
}
Java
// Java program to sink odd nodes to the bottom of
// binary tree
import java.util.*;
class GFG
{
// A binary tree node
static class Node
{
int data;
Node left, right;
};
// returns a new tree Node
static Node newnode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// Helper function to check if node is leaf node
static boolean isLeaf(Node root)
{
if(root==null){
return false;
}
return (root.left == null && root.right == null)?true:false;
}
// A recursive method to sink a tree with odd root
// This method assumes that the subtrees are already
// sinked. This method is similar to Heapify of
// Heap-Sort
static void sink(Node root)
{
// If NULL or is a leaf, do nothing
if (root == null || isLeaf(null))
return;
// if left subtree exists and left child is even
if (root.left!=null && (root.left.data & 1)==0)
{
// swap root's data with left child and
// fix left subtree
int temp = root.data;
root.data=root.left.data;
root.left.data=temp;
sink(root.left);
}
// if right subtree exists and right child is even
else if(root.right!=null && (root.right.data & 1)==0)
{
// swap root's data with right child and
// fix right subtree
int temp = root.data;
root.data=root.right.data;
root.right.data=temp;
sink(root.right);
}
}
// Function to sink all odd nodes to the bottom of binary
// tree. It does a postorder traversal and calls sink()
// if any odd node is found
static void sinkOddNodes(Node root)
{
// If NULL or is a leaf, do nothing
if (root == null || isLeaf(root))
return;
// Process left and right subtrees before this node
sinkOddNodes(root.left);
sinkOddNodes(root.right);
// If root is odd, sink it
if ((root.data & 1)!=0)
sink(root);
}
// Helper function to do Level Order Traversal of
// Binary Tree level by level. This function is used
// here only for showing modified tree.
static void printLevelOrder(Node root)
{
Queue<Node> q = new LinkedList<>();
q.add(root);
// Do Level order traversal
while (!q.isEmpty())
{
int nodeCount = q.size();
// Print one level at a time
while (nodeCount>0)
{
Node node = q.poll();
System.out.print(node.data+" ");
if (node.left != null)
q.add(node.left);
if (node.right != null)
q.add(node.right);
nodeCount--;
}
// Line separator for levels
System.out.println("");
}
}
// Driver code
public static void main(String[] args)
{
/* Constructed binary tree is
1
/ \
5 8
/ \ / \
2 4 9 10 */
Node root = newnode(1);
root.left = newnode(5);
root.right = newnode(8);
root.left.left = newnode(2);
root.left.right = newnode(4);
root.right.left = newnode(9);
root.right.right = newnode(10);
sinkOddNodes(root);
System.out.print("Level order traversal of modified tree\n");
printLevelOrder(root);
}
}
/* This code is contributed by shruti456rawal */
Python3
# Python3 program to sink odd nodes
# to the bottom of binary tree
# A binary tree node
# Helper function to allocates a new node
class newnode:
# Constructor to create a new node
def __init__(self, key):
self.data = key
self.left = None
self.right = None
# Helper function to check
# if node is leaf node
def isLeaf(root):
return (root.left == None and
root.right == None)
# A recursive method to sink a tree with odd root
# This method assumes that the subtrees are
# already sinked. This method is similar to
# Heapify of Heap-Sort
def sink(root):
# If None or is a leaf, do nothing
if (root == None or isLeaf(root)):
return
# if left subtree exists and
# left child is even
if (root.left and not(root.left.data & 1)):
# swap root's data with left child
# and fix left subtree
root.data, \
root.left.data = root.left.data, \
root.data
sink(root.left)
# if right subtree exists and
# right child is even
else if(root.right and not(root.right.data & 1)):
# swap root's data with right child
# and fix right subtree
root.data, \
root.right.data = root.right.data, \
root.data
sink(root.right)
# Function to sink all odd nodes to
# the bottom of binary tree. It does
# a postorder traversal and calls sink()
# if any odd node is found
def sinkOddNodes(root):
# If None or is a leaf, do nothing
if (root == None or isLeaf(root)):
return
# Process left and right subtrees
# before this node
sinkOddNodes(root.left)
sinkOddNodes(root.right)
# If root is odd, sink it
if (root.data & 1):
sink(root)
# Helper function to do Level Order Traversal
# of Binary Tree level by level. This function
# is used here only for showing modified tree.
def printLevelOrder(root):
q = []
q.append(root)
# Do Level order traversal
while (len(q)):
nodeCount = len(q)
# Print one level at a time
while (nodeCount):
node = q[0]
print(node.data, end = " ")
q.pop(0)
if (node.left != None):
q.append(node.left)
if (node.right != None):
q.append(node.right)
nodeCount -= 1
# Line separator for levels
print()
# Driver Code
""" Constructed binary tree is
1
/ \
5 8
/ \ / \
2 4 9 10 """
root = newnode(1)
root.left = newnode(5)
root.right = newnode(8)
root.left.left = newnode(2)
root.left.right = newnode(4)
root.right.left = newnode(9)
root.right.right = newnode(10)
sinkOddNodes(root)
print("Level order traversal of modified tree")
printLevelOrder(root)
# This code is contributed by SHUBHAMSINGH10
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA