Dado un árbol binario de Nodes distintos y un par de Nodes. La tarea es encontrar e imprimir la ruta entre los dos Nodes dados en el árbol binario.
Ejemplos:
Entrada: N1 = 7, N2 = 4
Salida: 7 3 1 4
Enfoque: En este artículo se ha discutido un enfoque para resolver este problema . En este artículo, se discutirá un enfoque recursivo incluso optimizado.
En este enfoque recursivo, a continuación se muestran los pasos:
- Encuentre el primer valor recursivamente, una vez encontrado, agregue el valor a la pila.
- Ahora, cada Node que se visita, ya sea en el seguimiento hacia atrás o hacia adelante, agrega los valores a la pila, pero si el Node se agregó en el seguimiento hacia adelante, elimínelo en el seguimiento hacia atrás y continúe hasta que se encuentre el segundo valor o se visiten todos los Nodes.
Por ejemplo: Considere que el camino entre 7 y 9 se encuentra en el árbol anterior. Atravesamos el árbol como DFS, una vez que encontramos el valor 7, lo agregamos a la pila. Atravesando la ruta 0 -> 1 -> 3 -> 7.
Ahora, mientras retrocede, agregue 3 y 1 a la pila. Entonces, a partir de ahora, la pila tiene [7, 3, 1], el hijo 1 tiene un hijo derecho, así que primero lo agregamos a la pila. Ahora, la pila contiene [7, 3, 1, 4]. Visite el hijo izquierdo de 4, agréguelo a la pila. La pila contiene [7, 3, 1, 4, 8] ahora. Dado que no hay más Nodes, volveríamos al Node anterior y dado que 8 ya se agregó a la pila, elimínelo. Ahora el Node 4 tiene un hijo correcto y lo agregamos a la pila, ya que este es el segundo valor que buscábamos, no habrá más llamadas recursivas. Finalmente, la pila contiene [7, 3, 1, 4, 9].
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// A binary tree node
class Node {
public:
int value;
Node *left, *right;
Node(int value) {
this->value = value;
left = NULL;
right = NULL;
}
};
bool firstValueFound = false;
bool secondValueFound = false;
stack<Node *> stk;
Node *root = NULL;
// Function to find the path between
// two nodes in binary tree
void pathBetweenNode(Node *root, int v1, int v2) {
// Base condition
if (root == NULL) return;
// If both the values are found then return
if (firstValueFound && secondValueFound) return;
// Starting the stack frame with
// isAddedToStack = false flag
bool isAddedToStack = false;
// If one of the value is found then add the
// value to the stack and make the isAddedToStack = true
if (firstValueFound ^ secondValueFound) {
stk.push(root);
isAddedToStack = true;
}
// If none of the two values is found
if (!(firstValueFound && secondValueFound)) {
pathBetweenNode(root->left, v1, v2);
}
// Copy of current state of firstValueFound
// and secondValueFound flag
bool localFirstValueFound = firstValueFound;
bool localSecondValueFound = secondValueFound;
// If the first value is found
if (root->value == v1) firstValueFound = true;
// If the second value is found
if (root->value == v2) secondValueFound = true;
bool localAdded = false;
// If one of the value is found and the value
// was not added to the stack yet or there was
// only one value found and now both the values
// are found and was not added to
// the stack then add it
if (((firstValueFound ^ secondValueFound) ||
((localFirstValueFound ^ localSecondValueFound) &&
(firstValueFound && secondValueFound))) &&
!isAddedToStack) {
localAdded = true;
stk.push(root);
}
// If none of the two values is found yet
if (!(firstValueFound && secondValueFound)) {
pathBetweenNode(root->right, v1, v2);
}
if ((firstValueFound ^ secondValueFound) && !isAddedToStack && !localAdded)
stk.push(root);
if ((firstValueFound ^ secondValueFound) && isAddedToStack) stk.pop();
}
// Function to find the path between
// two nodes in binary tree
stack<Node *> pathBetweenNode(int v1, int v2)
{
// Global root
pathBetweenNode(::root, v1, v2);
// If both the values are found
// then return the stack
if (firstValueFound && secondValueFound)
{
// Global Stack Object
return ::stk;
}
// If none of the two values is
// found then return empty stack
stack<Node *> stk;
return stk;
}
// Recursive function to print the
// contents of a stack in reverse
void print(stack<Node *> stk)
{
// If the stack is empty
if (stk.empty()) return;
// Get the top value
int value = stk.top()->value;
stk.pop();
// Recursive call
print(stk);
// Print the popped value
cout << value << " ";
}
// Driver code
int main(int argc, char const *argv[])
{
root = new Node(0);
root->left = new Node(1);
root->right = new Node(2);
root->left->left = new Node(3);
root->left->right = new Node(4);
root->right->left = new Node(5);
root->right->right = new Node(6);
root->left->left->left = new Node(7);
root->left->right->left = new Node(8);
root->left->right->right = new Node(9);
// Find and print the path
stack<Node *> stck = pathBetweenNode(7, 4);
print(stck);
}
// This code is contributed by sanjeev2552
Java
// Java implementation of the approach
import java.util.Stack;
public class GFG {
// A binary tree node
private static class Node {
public Node left;
public int value;
public Node right;
public Node(int value)
{
this.value = value;
left = null;
right = null;
}
}
private boolean firstValueFound = false;
private boolean secondValueFound = false;
private Stack<Node> stack = new Stack<Node>();
private Node root = null;
public GFG(Node root)
{
this.root = root;
}
// Function to find the path between
// two nodes in binary tree
public Stack<Node> pathBetweenNode(int v1, int v2)
{
pathBetweenNode(this.root, v1, v2);
// If both the values are found
// then return the stack
if (firstValueFound && secondValueFound) {
return stack;
}
// If none of the two values is
// found then return empty stack
return new Stack<Node>();
}
// Function to find the path between
// two nodes in binary tree
private void pathBetweenNode(Node root, int v1, int v2)
{
// Base condition
if (root == null)
return;
// If both the values are found then return
if (firstValueFound && secondValueFound)
return;
// Starting the stack frame with
// isAddedToStack = false flag
boolean isAddedToStack = false;
// If one of the value is found then add the
// value to the stack and make the isAddedToStack = true
if (firstValueFound ^ secondValueFound) {
stack.add(root);
isAddedToStack = true;
}
// If none of the two values is found
if (!(firstValueFound && secondValueFound)) {
pathBetweenNode(root.left, v1, v2);
}
// Copy of current state of firstValueFound
// and secondValueFound flag
boolean localFirstValueFound = firstValueFound;
boolean localSecondValueFound = secondValueFound;
// If the first value is found
if (root.value == v1)
firstValueFound = true;
// If the second value is found
if (root.value == v2)
secondValueFound = true;
boolean localAdded = false;
// If one of the value is found and the value
// was not added to the stack yet or there was
// only one value found and now both the values
// are found and was not added to
// the stack then add it
if (((firstValueFound ^ secondValueFound)
|| ((localFirstValueFound ^ localSecondValueFound)
&& (firstValueFound && secondValueFound)))
&& !isAddedToStack) {
localAdded = true;
stack.add(root);
}
// If none of the two values is found yet
if (!(firstValueFound && secondValueFound)) {
pathBetweenNode(root.right, v1, v2);
}
if ((firstValueFound ^ secondValueFound)
&& !isAddedToStack && !localAdded)
stack.add(root);
if ((firstValueFound ^ secondValueFound)
&& isAddedToStack)
stack.pop();
}
// Recursive function to print the
// contents of a stack in reverse
private static void print(Stack<Node> stack)
{
// If the stack is empty
if (stack.isEmpty())
return;
// Get the top value
int value = stack.pop().value;
// Recursive call
print(stack);
// Print the popped value
System.out.print(value + " ");
}
// Driver code
public static void main(String[] args)
{
Node root = new Node(0);
root.left = new Node(1);
root.right = new Node(2);
root.left.left = new Node(3);
root.left.right = new Node(4);
root.right.left = new Node(5);
root.right.right = new Node(6);
root.left.left.left = new Node(7);
root.left.right.left = new Node(8);
root.left.right.right = new Node(9);
// Find and print the path
GFG pathBetweenNodes = new GFG(root);
Stack<Node> stack
= pathBetweenNodes.pathBetweenNode(7, 4);
print(stack);
}
}
Python3
# Python3 implementation of # the above approach # A binary tree node class Node: def __init__(self, value): self.left = None self.right = None self.value = value firstValueFound = False secondValueFound = False stack = [] root = None # Function to find the path # between two nodes in binary # tree def pathBetweennode(v1, v2): global firstValueFound, secondValueFound pathBetweenNode(root, v1, v2) # If both the values are found # then return the stack if (firstValueFound and secondValueFound): return stack # If none of the two values is # found then return empty stack return [] # Function to find the path # between two nodes in binary # tree def pathBetweenNode(root, v1, v2): global firstValueFound, secondValueFound # Base condition if (root == None): return # If both the values are found # then return if (firstValueFound and secondValueFound): return # Starting the stack frame with # isAddedToStack = false flag isAddedToStack = False # If one of the value is found # then add the value to the # stack and make the isAddedToStack = true if (firstValueFound ^ secondValueFound): stack.append(root) isAddedToStack = True # If none of the two values # is found if (not (firstValueFound and secondValueFound)): pathBetweenNode(root.left, v1, v2) # Copy of current state of # firstValueFound and # secondValueFound flag localFirstValueFound = firstValueFound localSecondValueFound = secondValueFound # If the first value is found if (root.value == v1): firstValueFound = True # If the second value is found if (root.value == v2): secondValueFound = True localAdded = False # If one of the value is found # and the value was not added # to the stack yet or there was # only one value found and now # both the values are found and # was not added to the stack # then add it if (((firstValueFound ^ secondValueFound) or ((localFirstValueFound ^ localSecondValueFound) and (firstValueFound and secondValueFound))) and not isAddedToStack): localAdded = True stack.append(root) # If none of the two values # is found yet if (not (firstValueFound and secondValueFound)): pathBetweenNode(root.right, v1, v2) if ((firstValueFound ^ secondValueFound) and not isAddedToStack and not localAdded): stack.append(root) if ((firstValueFound ^ secondValueFound) and isAddedToStack): stack.pop() # Recursive function to print # the contents of a stack in # reverse def pri(stack): # If the stack is empty if (len(stack) == 0): return # Get the top value value = stack.pop().value # Recursive call pri(stack) # Print the popped value print(value, end = " ") # Driver code if __name__ == "__main__": root = Node(0) root.left = Node(1) root.right = Node(2) root.left.left = Node(3) root.left.right = Node(4) root.right.left = Node(5) root.right.right = Node(6) root.left.left.left = Node(7) root.left.right.left = Node(8) root.left.right.right = Node(9) # Find and print the path stack = pathBetweennode(7, 4) pri(stack) # This code is contributed by Rutvik_56
C#
// C# implementation of the approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG
{
// A binary tree node
public class Node
{
public Node left;
public int value;
public Node right;
public Node(int value)
{
this.value = value;
left = null;
right = null;
}
}
private Boolean firstValueFound = false;
private Boolean secondValueFound = false;
private Stack<Node> stack = new Stack<Node>();
private Node root = null;
public GFG(Node root)
{
this.root = root;
}
// Function to find the path between
// two nodes in binary tree
public Stack<Node> pathBetweenNode(int v1, int v2)
{
pathBetweenNode(this.root, v1, v2);
// If both the values are found
// then return the stack
if (firstValueFound && secondValueFound)
{
return stack;
}
// If none of the two values is
// found then return empty stack
return new Stack<Node>();
}
// Function to find the path between
// two nodes in binary tree
private void pathBetweenNode(Node root, int v1, int v2)
{
// Base condition
if (root == null)
return;
// If both the values are found then return
if (firstValueFound && secondValueFound)
return;
// Starting the stack frame with
// isAddedToStack = false flag
Boolean isAddedToStack = false;
// If one of the value is found then add the
// value to the stack and make the isAddedToStack = true
if (firstValueFound ^ secondValueFound)
{
stack.Push(root);
isAddedToStack = true;
}
// If none of the two values is found
if (!(firstValueFound && secondValueFound))
{
pathBetweenNode(root.left, v1, v2);
}
// Copy of current state of firstValueFound
// and secondValueFound flag
Boolean localFirstValueFound = firstValueFound;
Boolean localSecondValueFound = secondValueFound;
// If the first value is found
if (root.value == v1)
firstValueFound = true;
// If the second value is found
if (root.value == v2)
secondValueFound = true;
Boolean localAdded = false;
// If one of the value is found and the value
// was not added to the stack yet or there was
// only one value found and now both the values
// are found and was not added to
// the stack then add it
if (((firstValueFound ^ secondValueFound)
|| ((localFirstValueFound ^ localSecondValueFound)
&& (firstValueFound && secondValueFound)))
&& !isAddedToStack)
{
localAdded = true;
stack.Push(root);
}
// If none of the two values is found yet
if (!(firstValueFound && secondValueFound))
{
pathBetweenNode(root.right, v1, v2);
}
if ((firstValueFound ^ secondValueFound)
&& !isAddedToStack && !localAdded)
stack.Push(root);
if ((firstValueFound ^ secondValueFound)
&& isAddedToStack)
stack.Pop();
}
// Recursive function to print the
// contents of a stack in reverse
private static void print(Stack<Node> stack)
{
// If the stack is empty
if (stack.Count==0)
return;
// Get the top value
int value = stack.Pop().value;
// Recursive call
print(stack);
// Print the Popped value
Console.Write(value + " ");
}
// Driver code
public static void Main(String []args)
{
Node root = new Node(0);
root.left = new Node(1);
root.right = new Node(2);
root.left.left = new Node(3);
root.left.right = new Node(4);
root.right.left = new Node(5);
root.right.right = new Node(6);
root.left.left.left = new Node(7);
root.left.right.left = new Node(8);
root.left.right.right = new Node(9);
// Find and print the path
GFG pathBetweenNodes = new GFG(root);
Stack<Node> stack
= pathBetweenNodes.pathBetweenNode(7, 4);
print(stack);
}
}
// This code is contributed by Arnab Kundu
Javascript
<script>
// JavaScript implementation of the approach
// A binary tree node
class Node {
constructor(value) {
this.left = null;
this.right = null;
this.value = value;
}
}
let firstValueFound = false;
let secondValueFound = false;
let stack = [];
let root = null;
// Function to find the path between
// two nodes in binary tree
function path_BetweenNode(root, v1, v2)
{
// Base condition
if (root == null)
return;
// If both the values are found then return
if (firstValueFound && secondValueFound)
return;
// Starting the stack frame with
// isAddedToStack = false flag
let isAddedToStack = false;
// If one of the value is found then add the
// value to the stack and make the isAddedToStack = true
if (firstValueFound ^ secondValueFound) {
stack.push(root);
isAddedToStack = true;
}
// If none of the two values is found
if (!(firstValueFound && secondValueFound)) {
path_BetweenNode(root.left, v1, v2);
}
// Copy of current state of firstValueFound
// and secondValueFound flag
let localFirstValueFound = firstValueFound;
let localSecondValueFound = secondValueFound;
// If the first value is found
if (root.value == v1)
firstValueFound = true;
// If the second value is found
if (root.value == v2)
secondValueFound = true;
let localAdded = false;
// If one of the value is found and the value
// was not added to the stack yet or there was
// only one value found and now both the values
// are found and was not added to
// the stack then add it
if (((firstValueFound ^ secondValueFound)
|| ((localFirstValueFound ^ localSecondValueFound)
&& (firstValueFound && secondValueFound)))
&& !isAddedToStack) {
localAdded = true;
stack.push(root);
}
// If none of the two values is found yet
if (!(firstValueFound && secondValueFound)) {
path_BetweenNode(root.right, v1, v2);
}
if ((firstValueFound ^ secondValueFound)
&& !isAddedToStack && !localAdded)
stack.push(root);
if ((firstValueFound ^ secondValueFound)
&& isAddedToStack)
stack.pop();
}
// Function to find the path between
// two nodes in binary tree
function pathBetweenNode(v1, v2)
{
path_BetweenNode(root, v1, v2);
// If both the values are found
// then return the stack
if (firstValueFound && secondValueFound) {
return stack;
}
// If none of the two values is
// found then return empty stack
return [];
}
// Recursive function to print the
// contents of a stack in reverse
function print(stack)
{
// If the stack is empty
if (stack.length == 0)
return;
// Get the top value
let value = stack[stack.length - 1].value;
stack.pop();
// Recursive call
print(stack);
// Print the popped value
document.write(value + " ");
}
root = new Node(0);
root.left = new Node(1);
root.right = new Node(2);
root.left.left = new Node(3);
root.left.right = new Node(4);
root.right.left = new Node(5);
root.right.right = new Node(6);
root.left.left.left = new Node(7);
root.left.right.left = new Node(8);
root.left.right.right = new Node(9);
// Find and print the path
stack = pathBetweenNode(7, 4);
print(stack);
</script>
Producción:
7 3 1 4
Publicación traducida automáticamente
Artículo escrito por Imran_Hossain_Faruk y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA