Compruebe si una array determinada puede representar el recorrido de pedido previo del árbol de búsqueda binaria

Dada una array de números, devuelve verdadero si la array dada puede representar un recorrido de preorden de un árbol de búsqueda binario, de lo contrario, devuelve falso. La complejidad de tiempo esperada es O(n).

Ejemplos:

C++

// C++ program for an efficient solution to check if
// a given array can represent Preorder traversal of
// a Binary Search Tree
#include<bits/stdc++.h>
using namespace std;
 
bool canRepresentBST(int pre[], int n)
{
    // Create an empty stack
    stack<int> s;
 
    // Initialize current root as minimum possible
    // value
    int root = INT_MIN;
 
    // Traverse given array
    for (int i=0; i<n; i++)
    {
        // If we find a node who is on right side
        // and smaller than root, return false
        if (pre[i] < root)
            return false;
 
        // If pre[i] is in right subtree of stack top,
        // Keep removing items smaller than pre[i]
        // and make the last removed item as new
        // root.
        while (!s.empty() && s.top()<pre[i])
        {
            root = s.top();
            s.pop();
        }
 
        // At this point either stack is empty or
        // pre[i] is smaller than root, push pre[i]
        s.push(pre[i]);
    }
    return true;
}
 
// Driver program
int main()
{
    int pre1[] = {40, 30, 35, 80, 100};
    int n = sizeof(pre1)/sizeof(pre1[0]);
    canRepresentBST(pre1, n)? cout << "true\n":
                              cout << "false\n";
 
    int pre2[] = {40, 30, 35, 20, 80, 100};
    n = sizeof(pre2)/sizeof(pre2[0]);
    canRepresentBST(pre2, n)? cout << "true\n":
                              cout << "false\n";
 
    return 0;
}

Java

// Java program for an efficient solution to check if
// a given array can represent Preorder traversal of
// a Binary Search Tree
import java.util.Stack;
   
class BinarySearchTree {
   
    boolean canRepresentBST(int pre[], int n) {
        // Create an empty stack
        Stack<Integer> s = new Stack<Integer>();
   
        // Initialize current root as minimum possible
        // value
        int root = Integer.MIN_VALUE;
   
        // Traverse given array
        for (int i = 0; i < n; i++) {
            // If we find a node who is on right side
            // and smaller than root, return false
            if (pre[i] < root) {
                return false;
            }
   
            // If pre[i] is in right subtree of stack top,
            // Keep removing items smaller than pre[i]
            // and make the last removed item as new
            // root.
            while (!s.empty() && s.peek() < pre[i]) {
                root = s.peek();
                s.pop();
            }
   
            // At this point either stack is empty or
            // pre[i] is smaller than root, push pre[i]
            s.push(pre[i]);
        }
        return true;
    }
   
    public static void main(String args[]) {
        BinarySearchTree bst = new BinarySearchTree();
        int[] pre1 = new int[]{40, 30, 35, 80, 100};
        int n = pre1.length;
        if (bst.canRepresentBST(pre1, n) == true) {
            System.out.println("true");
        } else {
            System.out.println("false");
        }
        int[] pre2 = new int[]{40, 30, 35, 20, 80, 100};
        int n1 = pre2.length;
        if (bst.canRepresentBST(pre2, n) == true) {
            System.out.println("true");
        } else {
            System.out.println("false");
        }
    }
}
   
//This code is contributed by Mayank Jaiswal

Python3

# Python program for an efficient solution to check if
# a given array can represent Preorder traversal of
# a Binary Search Tree
 
INT_MIN = -2**32
 
def canRepresentBST(pre):
 
    # Create an empty stack
    s = []
 
    # Initialize current root as minimum possible value
    root = INT_MIN
 
    # Traverse given array
    for value in pre:
        #NOTE:value is equal to pre[i] according to the
        #given algo  
     
        # If we find a node who is on the right side
        # and smaller than root, return False
        if value < root :
            return False
     
        # If value(pre[i]) is in right subtree of stack top,
        # Keep removing items smaller than value
        # and make the last removed items as new root
        while(len(s) > 0 and s[-1] < value) :
            root = s.pop()
         
        # At this point either stack is empty or value
        # is smaller than root, push value
        s.append(value)
 
    return True
 
# Driver Program
pre1 = [40 , 30 , 35 , 80 , 100]
print ("true" if canRepresentBST(pre1) == True else "false")
pre2 = [40 , 30 , 35 , 20 ,  80 , 100]
print ("true" if canRepresentBST(pre2) == True else "false")
 
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

C#

// C# program for an efficient solution
// to check if a given array can represent 
// Preorder traversal of a Binary Search Tree
using System;
using System.Collections.Generic;
 
class GFG
{
 
public virtual bool canRepresentBST(int[] pre, int n)
{
    // Create an empty stack
    Stack<int> s = new Stack<int>();
 
    // Initialize current root as minimum
    // possible value
    int root = int.MinValue;
 
    // Traverse given array
    for (int i = 0; i < n; i++)
    {
        // If we find a node who is on right side
        // and smaller than root, return false
        if (pre[i] < root)
        {
            return false;
        }
 
        // If pre[i] is in right subtree of stack top,
        // Keep removing items smaller than pre[i]
        // and make the last removed item as new
        // root.
        while (s.Count > 0 && s.Peek() < pre[i])
        {
            root = s.Peek();
            s.Pop();
        }
 
        // At this point either stack is empty or
        // pre[i] is smaller than root, push pre[i]
        s.Push(pre[i]);
    }
    return true;
}
 
// Driver Code
public static void Main(string[] args)
{
    GFG bst = new GFG();
    int[] pre1 = new int[]{40, 30, 35, 80, 100};
    int n = pre1.Length;
    if (bst.canRepresentBST(pre1, n) == true)
    {
        Console.WriteLine("true");
    }
    else
    {
        Console.WriteLine("false");
    }
    int[] pre2 = new int[]{40, 30, 35, 20, 80, 100};
    int n1 = pre2.Length;
    if (bst.canRepresentBST(pre2, n) == true)
    {
        Console.WriteLine("true");
    }
    else
    {
        Console.WriteLine("false");
    }
}
}
 
// This code is contributed by Shrikant13

Javascript

<script>
 
// Javascript program for an efficient
// solution to check if a given array
// can represent Preorder traversal of
// a Binary Search Tree
function canRepresentBST(pre, n)
{
     
    // Create an empty stack
    var s = [];
 
    // Initialize current root as minimum possible
    // value
    var root = -1000000000;
 
    // Traverse given array
    for(var i = 0; i < n; i++)
    {
         
        // If we find a node who is on right side
        // and smaller than root, return false
        if (pre[i] < root)
            return false;
 
        // If pre[i] is in right subtree of stack top,
        // Keep removing items smaller than pre[i]
        // and make the last removed item as new
        // root.
        while (s.length != 0 && s[s.length - 1] < pre[i])
        {
            root = s[s.length - 1];
            s.pop();
        }
 
        // At this point either stack is empty or
        // pre[i] is smaller than root, push pre[i]
        s.push(pre[i]);
    }
    return true;
}
 
// Driver code
var pre1 = [ 40, 30, 35, 80, 100 ];
var n = pre1.length;
canRepresentBST(pre1, n) ? document.write("true<br>"):
                           document.write("false<br>");
var pre2 = [ 40, 30, 35, 20, 80, 100 ];
n = pre2.length;
canRepresentBST(pre2, n) ? document.write("true"):
                           document.write("false");
 
// This code is contributed by importantly
 
</script>

C++

// C++ program to illustrate if a given array can represent
// a preorder traversal of a BST or not
 
#include <bits/stdc++.h>
using namespace std;
 
// We are actually not building the tree
void buildBST_helper(int& preIndex, int n, int pre[],
                     int min, int max)
{
    if (preIndex >= n)
        return;
 
    if (min <= pre[preIndex] && pre[preIndex] <= max) {
        // build node
        int rootData = pre[preIndex];
        preIndex++;
 
        // build left subtree
        buildBST_helper(preIndex, n, pre, min, rootData);
 
        // build right subtree
        buildBST_helper(preIndex, n, pre, rootData, max);
    }
    // else
    // return NULL;
}
 
bool canRepresentBST(int arr[], int N)
{
    // code here
    int min = INT_MIN, max = INT_MAX;
    int preIndex = 0;
 
    buildBST_helper(preIndex, N, arr, min, max);
 
    return preIndex == N;
}
 
// Driver Code
int main()
{
 
    int preorder1[] = { 2, 4, 3 };
    /*
            2
            \
             4
            /
           3
 
*/
    int n1 = sizeof(preorder1) / sizeof(preorder1[0]);
 
    if (canRepresentBST(preorder1, n1))
        cout << "\npreorder1 can represent BST";
    else
        cout << "\npreorder1 can not represent BST  :(";
 
    int preorder2[] = { 5, 3, 4, 1, 6, 10 };
    int n2 = sizeof(preorder2) / sizeof(preorder2[0]);
    /*
                    5
         /     \
       3         1
         \     /  \
         4    6    10
 
*/
    if (canRepresentBST(preorder2, n2))
        cout << "\npreorder2 can represent BST";
    else
        cout << "\npreorder2 can not represent BST  :(";
 
    int preorder3[] = { 5, 3, 4, 8, 6, 10 };
    int n3 = sizeof(preorder3) / sizeof(preorder3[0]);
    /*
                    5
         /     \
       3         8
         \     /  \
         4    6    10
 
*/
    if (canRepresentBST(preorder3, n3))
        cout << "\npreorder3 can represent BST";
    else
        cout << "\npreorder3 can not represent BST  :(";
 
    return 0;
}
 
// This code is contributed by Sourashis Mondal

Java

// Java program to illustrate if a given array can represent
// a preorder traversal of a BST or not
public class Main
{
    static int preIndex = 0;
      
    // We are actually not building the tree
    static void buildBST_helper(int n, int[] pre, int min, int max)
    {
        if (preIndex >= n)
            return;
   
        if (min <= pre[preIndex] && pre[preIndex] <= max) {
           
            // build node
            int rootData = pre[preIndex];
            preIndex++;
   
            // build left subtree
            buildBST_helper(n, pre, min, rootData);
   
            // build right subtree
            buildBST_helper(n, pre, rootData, max);
        }
        // else
        // return NULL;
    }
   
    static boolean canRepresentBST(int[] arr, int N)
    {
        // code here
        int min = Integer.MIN_VALUE, max = Integer.MAX_VALUE;
   
        buildBST_helper(N, arr, min, max);
   
        return preIndex == N;
    }
     
    public static void main(String[] args) {
        int[] preorder1 = { 2, 4, 3 };
        /*
                2
                \
                 4
                /
               3
        */
        int n1 = preorder1.length;
        System.out.println();
        if (canRepresentBST(preorder1, n1))
            System.out.print("preorder1 can represent BST");
        else
            System.out.print("preorder1 can not represent BST  :(");
       
        int[] preorder2 = { 5, 3, 4, 1, 6, 10 };
        int n2 = preorder2.length;
        System.out.println();
        /*
                        5
             /     \
           3         1
             \     /  \
             4    6    10
        */
        if (!canRepresentBST(preorder2, n2))
            System.out.print("preorder2 can represent BST");
        else
            System.out.print("preorder2 can not represent BST  :(");
       
        int[] preorder3 = { 5, 3, 4, 8, 6, 10 };
        int n3 = preorder3.length;
        System.out.println();
        /*
                        5
             /     \
           3         8
             \     /  \
             4    6    10
        */
        if (canRepresentBST(preorder3, n3))
            System.out.print("preorder3 can represent BST");
        else
            System.out.print("preorder3 can not represent BST  :(");
    }
}
 
// This code is contributed by mukesh07.

Python3

# Python3 program to illustrate if a given array can represent
# a preorder traversal of a BST or not
import sys
 
preIndex = 0
      
# We are actually not building the tree
def buildBST_helper(n, pre, Min, Max):
    global preIndex
    if (preIndex >= n):
        return
 
    if (Min <= pre[preIndex] and pre[preIndex] <= Max):
        # build node
        rootData = pre[preIndex]
        preIndex+=1
 
        # build left subtree
        buildBST_helper(n, pre, Min, rootData)
 
        # build right subtree
        buildBST_helper(n, pre, rootData, Max)
    # else
    # return NULL
 
def canRepresentBST(arr, N):
    global preIndex
    # code here
    Min, Max = sys.maxsize, -sys.maxsize
 
    buildBST_helper(N, arr, Min, Max)
     
    if preIndex == N:
        return True
 
    return False
  
preorder1 = [ 2, 4, 3 ]
"""
        2
        \
         4
        /
       3
 
"""
n1 = len(preorder1)
 
if (not canRepresentBST(preorder1, n1)):
  print("preorder1 can represent BST");
else:
  print("preorder1 can not represent BST  :(")
 
preorder2 = [ 5, 3, 4, 1, 6, 10 ]
n2 = len(preorder2)
"""
                      5
           /     \
         3         1
           \     /  \
           4    6    10
 
"""
if (canRepresentBST(preorder2, n2)):
  print("preorder2 can represent BST")
else:
  print("preorder2 can not represent BST  :(")
 
preorder3 = [ 5, 3, 4, 8, 6, 10 ]
n3 = len(preorder3)
"""
                      5
           /     \
         3         8
           \     /  \
           4    6    10
"""
if (not canRepresentBST(preorder3, n3)):
  print("preorder3 can represent BST")
else:
  print("preorder3 can not represent BST  :(")

C#

// C# program to illustrate if a given array can represent
// a preorder traversal of a BST or not
using System;
class GFG {
     
    static int preIndex = 0;
     
    // We are actually not building the tree
    static void buildBST_helper(int n, int[] pre, int min, int max)
    {
        if (preIndex >= n)
            return;
  
        if (min <= pre[preIndex] && pre[preIndex] <= max) {
            // build node
            int rootData = pre[preIndex];
            preIndex++;
  
            // build left subtree
            buildBST_helper(n, pre, min, rootData);
  
            // build right subtree
            buildBST_helper(n, pre, rootData, max);
        }
        // else
        // return NULL;
    }
  
    static bool canRepresentBST(int[] arr, int N)
    {
        // code here
        int min = Int32.MinValue, max = Int32.MaxValue;
  
        buildBST_helper(N, arr, min, max);
  
        return preIndex == N;
    }
     
  static void Main() {
    int[] preorder1 = { 2, 4, 3 };
    /*
            2
            \
             4
            /
           3
    */
    int n1 = preorder1.Length;
    Console.WriteLine();
    if (canRepresentBST(preorder1, n1))
        Console.Write("preorder1 can represent BST");
    else
        Console.Write("preorder1 can not represent BST  :(");
  
    int[] preorder2 = { 5, 3, 4, 1, 6, 10 };
    int n2 = preorder2.Length;
    Console.WriteLine();
    /*
                    5
         /     \
       3         1
         \     /  \
         4    6    10
    */
    if (!canRepresentBST(preorder2, n2))
        Console.Write("preorder2 can represent BST");
    else
        Console.Write("preorder2 can not represent BST  :(");
  
    int[] preorder3 = { 5, 3, 4, 8, 6, 10 };
    int n3 = preorder3.Length;
    Console.WriteLine();
    /*
                    5
         /     \
       3         8
         \     /  \
         4    6    10
    */
    if (canRepresentBST(preorder3, n3))
        Console.Write("preorder3 can represent BST");
    else
        Console.Write("preorder3 can not represent BST  :(");
  }
}
 
// This code is contributed by rameshtravel07.

Javascript

<script>
    // Javascript program to illustrate if a given array can represent
    // a preorder traversal of a BST or not
     
    let preIndex = 0;
     
    // We are actually not building the tree
    function buildBST_helper(n, pre, min, max)
    {
        if (preIndex >= n)
            return;
 
        if (min <= pre[preIndex] && pre[preIndex] <= max) {
            // build node
            let rootData = pre[preIndex];
            preIndex++;
 
            // build left subtree
            buildBST_helper(n, pre, min, rootData);
 
            // build right subtree
            buildBST_helper(n, pre, rootData, max);
        }
        // else
        // return NULL;
    }
 
    function canRepresentBST(arr, N)
    {
        // code here
        let min = Number.MIN_VALUE, max = Number.MAX_VALUE;
 
        buildBST_helper(N, arr, min, max);
 
        return preIndex == N;
    }
     
    let preorder1 = [ 2, 4, 3 ];
    /*
            2
            \
             4
            /
           3
  
    */
    let n1 = preorder1.length;
 
    if (canRepresentBST(preorder1, n1))
      document.write("</br>" + "preorder1 can represent BST");
    else
      document.write("</br>" + "preorder1 can not represent BST  :(");
 
    let preorder2 = [ 5, 3, 4, 1, 6, 10 ];
    let n2 = preorder2.length;
    /*
                          5
               /     \
             3         1
               \     /  \
               4    6    10
 
      */
    if (!canRepresentBST(preorder2, n2))
      document.write("</br>" + "preorder2 can represent BST");
    else
      document.write("</br>" + "preorder2 can not represent BST  :(");
 
    let preorder3 = [ 5, 3, 4, 8, 6, 10 ];
    let n3 = preorder3.length;
    /*
                          5
               /     \
             3         8
               \     /  \
               4    6    10
 
      */
    if (canRepresentBST(preorder3, n3))
      document.write("</br>" + "preorder3 can represent BST");
    else
      document.write("</br>" + "preorder3 can not represent BST  :(");
 
// This code is contributed by decode2207.
</script>

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *