Dado un árbol binario que consta de valores distintos y dos números K1 y K2 , la tarea es encontrar todos los Nodes que se encuentran entre ellos en la secuencia ordenada del árbol.
Ejemplos:
Entrada:
1
/ \
12 11
/ / \
3 4 13
\ /
15 9
k1 = 12
k2 = 15
Salida:
1 4
Explicación:
La secuencia en orden es 3 12 1 4 15 11 9 13
Los Nodes comunes entre 12 y 15 en el orden secuencia del árbol son {1, 4}.
Entrada:
5
/ \
21 77
/ \ \
61 16 36
\ /
10 3
/
23
k1 = 23
k2 = 3
Salida:
10 5 77
Explicación:
La secuencia en orden es 61 21 16 23 10 5 77 3 36
Los Nodes comunes entre 23 y 3 en la secuencia en orden del árbol son {10, 5, 77}.
Enfoque:
para resolver este problema, estamos utilizando el recorrido en orden de Morris de un árbol binario para evitar el uso de espacio adicional. Mantenemos una bandera para establecer cuando se encuentra K1 o K2. Una vez encontrado, imprima cada Node que aparece en la secuencia en orden hasta que se encuentre el otro Node.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to find
// the common nodes
// between given two nodes
// in the inorder sequence
// of the binary tree
#include <bits/stdc++.h>
using namespace std;
// Definition of Binary
// Tree Structure
struct tNode {
int data;
struct tNode* left;
struct tNode* right;
};
// Helper function to allocate
// memory to create new nodes
struct tNode* newtNode(int data)
{
struct tNode* node = new tNode;
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
}
// Flag to set if
// either of K1 or
// K2 is found
int flag = 0;
// Function to traverse the
// binary tree without recursion
// and without stack using
// Morris Traversal
void findCommonNodes(struct tNode* root,
int K1, int K2)
{
struct tNode *current, *pre;
if (root == NULL)
return;
current = root;
while (current != NULL) {
if (current->left == NULL) {
if (current->data == K1 || current->data == K2) {
if (flag) {
return;
}
else {
flag = 1;
}
}
else if (flag) {
cout << current->data << " ";
}
current = current->right;
}
else {
// Find the inorder predecessor
// of current
pre = current->left;
while (pre->right != NULL
&& pre->right != current)
pre = pre->right;
// Make current as the right
// child of its inorder
// predecessor
if (pre->right == NULL) {
pre->right = current;
current = current->left;
}
// Revert the changes made
// to restore the original tree
// i.e., fix the right child
// of predecessor
else {
pre->right = NULL;
if (current->data == K1 || current->data == K2) {
if (flag) {
return;
}
else {
flag = 1;
}
}
else if (flag) {
cout << current->data << " ";
}
current = current->right;
} // End of if condition pre->right == NULL
} // End of if condition current->left == NULL
} // End of while
}
// Driver code
int main()
{
struct tNode* root = newtNode(1);
root->left = newtNode(12);
root->right = newtNode(11);
root->left->left = newtNode(3);
root->right->left = newtNode(4);
root->right->right = newtNode(13);
root->right->left->right = newtNode(15);
root->right->right->left = newtNode(9);
int K1 = 12, K2 = 15;
findCommonNodes(root, K1, K2);
return 0;
}
Java
// Java program to find the common nodes
// between given two nodes in the inorder
// sequence of the binary tree
import java.util.*;
class GFG{
// Definition of Binary Tree
static class tNode
{
int data;
tNode left;
tNode right;
};
// Helper function to allocate
// memory to create new nodes
static tNode newtNode(int data)
{
tNode node = new tNode();
node.data = data;
node.left = null;
node.right = null;
return (node);
}
// Flag to set if either
// of K1 or K2 is found
static int flag = 0;
// Function to traverse the binary
// tree without recursion and
// without stack using
// Morris Traversal
static void findCommonNodes(tNode root,
int K1, int K2)
{
tNode current, pre;
if (root == null)
return;
current = root;
while (current != null)
{
if (current.left == null)
{
if (current.data == K1 ||
current.data == K2)
{
if (flag == 1)
{
return;
}
else
{
flag = 1;
}
}
else if (flag == 1)
{
System.out.print(current.data + " ");
}
current = current.right;
}
else
{
// Find the inorder predecessor
// of current
pre = current.left;
while (pre.right != null &&
pre.right != current)
{
pre = pre.right;
}
// Make current as the right
// child of its inorder
// predecessor
if (pre.right == null)
{
pre.right = current;
current = current.left;
}
// Revert the changes made
// to restore the original tree
// i.e., fix the right child
// of predecessor
else
{
pre.right = null;
if (current.data == K1 ||
current.data == K2)
{
if (flag == 1)
{
return;
}
else
{
flag = 1;
}
}
else if (flag == 1)
{
System.out.print(current.data + " ");
}
current = current.right;
} // End of if condition pre.right == null
} // End of if condition current.left == null
} // End of while
}
// Driver code
public static void main(String[] args)
{
tNode root = newtNode(1);
root.left = newtNode(12);
root.right = newtNode(11);
root.left.left = newtNode(3);
root.right.left = newtNode(4);
root.right.right = newtNode(13);
root.right.left.right = newtNode(15);
root.right.right.left = newtNode(9);
int K1 = 12, K2 = 15;
findCommonNodes(root, K1, K2);
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program for the # above approach from collections import deque # A Tree node class Node: def __init__(self, x): self.data = x self.left = None self.right = None # Flag to set if # either of K1 or # K2 is found flag = 0 # Function to traverse the # binary tree without recursion # and without stack using # Morris Traversal def findCommonNodes(root, K1, K2): global flag current, pre = None, None if (root == None): return current = root while (current != None): if (current.left == None): if (current.data == K1 or current.data == K2): if (flag): return else: flag = 1 elif (flag): print(current.data, end = " ") else: None current = current.right else: # Find the inorder # predecessor of current pre = current.left while (pre.right != None and pre.right != current): pre = pre.right # Make current as the right # child of its inorder # predecessor if (pre.right == None): pre.right = current current = current.left # Revert the changes made # to restore the original tree # i.e., fix the right child # of predecessor else: pre.right = None if (current.data == K1 or current.data == K2): if (flag): return else: flag = 1 elif (flag): print(current.data, end = " ") current = current.right # End of if condition # pre.right == None # End of if condition #current.left == None # End of while # Driver code if __name__ == '__main__': root = Node(1) root.left = Node(12) root.right = Node(11) root.left.left = Node(3) root.right.left = Node(4) root.right.right = Node(13) root.right.left.right = Node(15) root.right.right.left = Node(9) K1 = 12 K2 = 15 findCommonNodes(root, K1, K2) # This code is contributed by Mohit Kumar 29
C#
// C# program to find the common nodes
// between given two nodes in the inorder
// sequence of the binary tree
using System;
class GFG{
// Definition of Binary Tree
class tNode
{
public int data;
public tNode left;
public tNode right;
};
// Helper function to allocate
// memory to create new nodes
static tNode newtNode(int data)
{
tNode node = new tNode();
node.data = data;
node.left = null;
node.right = null;
return (node);
}
// Flag to set if either
// of K1 or K2 is found
static int flag = 0;
// Function to traverse the binary
// tree without recursion and
// without stack using
// Morris Traversal
static void findCommonNodes(tNode root,
int K1, int K2)
{
tNode current, pre;
if (root == null)
return;
current = root;
while (current != null)
{
if (current.left == null)
{
if (current.data == K1 ||
current.data == K2)
{
if (flag == 1)
{
return;
}
else
{
flag = 1;
}
}
else if (flag == 1)
{
Console.Write(current.data + " ");
}
current = current.right;
}
else
{
// Find the inorder predecessor
// of current
pre = current.left;
while (pre.right != null &&
pre.right != current)
{
pre = pre.right;
}
// Make current as the right
// child of its inorder
// predecessor
if (pre.right == null)
{
pre.right = current;
current = current.left;
}
// Revert the changes made
// to restore the original tree
// i.e., fix the right child
// of predecessor
else
{
pre.right = null;
if (current.data == K1 ||
current.data == K2)
{
if (flag == 1)
{
return;
}
else
{
flag = 1;
}
}
else if (flag == 1)
{
Console.Write(current.data + " ");
}
current = current.right;
} // End of if condition pre.right == null
} // End of if condition current.left == null
} // End of while
}
// Driver code
public static void Main(String[] args)
{
tNode root = newtNode(1);
root.left = newtNode(12);
root.right = newtNode(11);
root.left.left = newtNode(3);
root.right.left = newtNode(4);
root.right.right = newtNode(13);
root.right.left.right = newtNode(15);
root.right.right.left = newtNode(9);
int K1 = 12, K2 = 15;
findCommonNodes(root, K1, K2);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program to find the common nodes
// between given two nodes in the inorder
// sequence of the binary tree
// Definition of Binary Tree
class Node
{
// Helper function to allocate
// memory to create new nodes
constructor(data)
{
this.data = data;
this.left = this.right=null;
}
}
// Flag to set if either
// of K1 or K2 is found
let flag = 0;
// Function to traverse the binary
// tree without recursion and
// without stack using
// Morris Traversal
function findCommonNodes(root, K1, K2)
{
let current, pre;
if (root == null)
return;
current = root;
while (current != null)
{
if (current.left == null)
{
if (current.data == K1 ||
current.data == K2)
{
if (flag == 1)
{
return;
}
else
{
flag = 1;
}
}
else if (flag == 1)
{
document.write(current.data + " ");
}
current = current.right;
}
else
{
// Find the inorder predecessor
// of current
pre = current.left;
while (pre.right != null &&
pre.right != current)
{
pre = pre.right;
}
// Make current as the right
// child of its inorder
// predecessor
if (pre.right == null)
{
pre.right = current;
current = current.left;
}
// Revert the changes made
// to restore the original tree
// i.e., fix the right child
// of predecessor
else
{
pre.right = null;
if (current.data == K1 ||
current.data == K2)
{
if (flag == 1)
{
return;
}
else
{
flag = 1;
}
}
else if (flag == 1)
{
document.write(current.data + " ");
}
current = current.right;
} // End of if condition pre.right == null
} // End of if condition current.left == null
} // End of while
}
// Driver code
let root = new Node(1);
root.left = new Node(12);
root.right = new Node(11);
root.left.left = new Node(3);
root.right.left = new Node(4);
root.right.right = new Node(13);
root.right.left.right = new Node(15);
root.right.right.left = new Node(9);
let K1 = 12, K2 = 15;
findCommonNodes(root, K1, K2);
// This code is contributed by patel2127
</script>
Producción:
1 4
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por MohammadMudassir y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA