如何根据给定的遍历构造BST？ |S1

本文概述

• C ++
• C
• Java
• python
• C#
• C ++
• C
• Java
• python
• C#

给定二元搜索树的遍历顺序, 构造BST。

例如, 如果给定的遍历为{10, 5, 1, 7, 40, 50}, 则输出应为以下树的根。

10
   /   \
  5     40
 /  \      \
1    7      50

方法1 (O(n^2)时间复杂度)

预遍历的第一个元素始终是根。我们首先构造根。然后我们找到第一个元素的索引, 该索引大于根。假设索引为" i"。根和" i"之间的值将成为左子树的一部分, 而" i + 1"和" n-1"之间的值将成为右子树的一部分。将给定的pre []划分为索引" i", 然后对左右子树重复进行。

例如在{10, 5, 1, 7, 40, 50}中, 10是第一个元素, 因此我们将其设为根。现在, 我们寻找第一个大于10的元素, 找到40。因此, 我们知道BST的结构如下。

10
           /    \
          /      \
  {5, 1, 7}       {40, 50}

我们对子数组{5, 1, 7}和{40, 50}递归地执行上述步骤, 并获得完整的树。

C ++

/* A O(n^2) program for construction of BST from preorder
  * traversal */
#include <bits/stdc++.h>
using namespace std;
 
/* A binary tree node has data, pointer to left child
and a pointer to right child */
class node
{
public :
     int data;
     node* left;
     node* right;
};
 
// A utility function to create a node
node* newNode( int data)
{
     node* temp = new node();
 
     temp->data = data;
     temp->left = temp->right = NULL;
 
     return temp;
}
 
// A recursive function to construct Full from pre[].
// preIndex is used to keep track of index in pre[].
node* constructTreeUtil( int pre[], int * preIndex, int low, int high, int size)
{
     // Base case
     if (*preIndex >= size || low > high)
         return NULL;
 
     // The first node in preorder traversal is root. So take
     // the node at preIndex from pre[] and make it root, and
     // increment preIndex
     node* root = newNode(pre[*preIndex]);
     *preIndex = *preIndex + 1;
 
     // If the current subarry has only one element, no need
     // to recur
     if (low == high)
         return root;
 
     // Search for the first element greater than root
     int i;
     for (i = low; i <= high; ++i)
         if (pre[i] > root->data)
             break ;
 
     // Use the index of element found in preorder to divide
     // preorder array in two parts. Left subtree and right
     // subtree
     root->left = constructTreeUtil(pre, preIndex, *preIndex, i - 1, size);
     root->right
         = constructTreeUtil(pre, preIndex, i, high, size);
 
     return root;
}
 
// The main function to construct BST from given preorder
// traversal. This function mainly uses constructTreeUtil()
node* constructTree( int pre[], int size)
{
     int preIndex = 0;
     return constructTreeUtil(pre, &preIndex, 0, size - 1, size);
}
 
// A utility function to print inorder traversal of a Binary
// Tree
void printInorder(node* node)
{
     if (node == NULL)
         return ;
     printInorder(node->left);
     cout << node->data << " " ;
     printInorder(node->right);
}
 
// Driver code
int main()
{
     int pre[] = { 10, 5, 1, 7, 40, 50 };
     int size = sizeof (pre) / sizeof (pre[0]);
 
     node* root = constructTree(pre, size);
 
     cout << "Inorder traversal of the constructed tree: \n" ;
     printInorder(root);
 
     return 0;
}
 
// This code is contributed by rathbhupendra

C

/* A O(n^2) program for construction of BST from preorder
  * traversal */
#include <stdio.h>
#include <stdlib.h>
 
/* A binary tree node has data, pointer to left child
    and a pointer to right child */
struct node
{
     int data;
     struct node* left;
     struct node* right;
};
 
// A utility function to create a node
struct node* newNode( int data)
{
     struct node* temp
         = ( struct node*) malloc ( sizeof ( struct node));
 
     temp->data = data;
     temp->left = temp->right = NULL;
 
     return temp;
}
 
// A recursive function to construct Full from pre[].
// preIndex is used to keep track of index in pre[].
struct node* constructTreeUtil( int pre[], int * preIndex, int low, int high, int size)
{
     // Base case
     if (*preIndex >= size || low > high)
         return NULL;
 
     // The first node in preorder traversal is root. So take
     // the node at preIndex from pre[] and make it root, and
     // increment preIndex
     struct node* root = newNode(pre[*preIndex]);
     *preIndex = *preIndex + 1;
 
     // If the current subarry has only one element, no need
     // to recur
     if (low == high)
         return root;
 
     // Search for the first element greater than root
     int i;
     for (i = low; i <= high; ++i)
         if (pre[i] > root->data)
             break ;
 
     // Use the index of element found in preorder to divide
     // preorder array in two parts. Left subtree and right
     // subtree
     root->left = constructTreeUtil(pre, preIndex, *preIndex, i - 1, size);
     root->right
         = constructTreeUtil(pre, preIndex, i, high, size);
 
     return root;
}
 
// The main function to construct BST from given preorder
// traversal. This function mainly uses constructTreeUtil()
struct node* constructTree( int pre[], int size)
{
     int preIndex = 0;
     return constructTreeUtil(pre, &preIndex, 0, size - 1, size);
}
 
// A utility function to print inorder traversal of a Binary
// Tree
void printInorder( struct node* node)
{
     if (node == NULL)
         return ;
     printInorder(node->left);
     printf ( "%d " , node->data);
     printInorder(node->right);
}
 
// Driver code
int main()
{
     int pre[] = { 10, 5, 1, 7, 40, 50 };
     int size = sizeof (pre) / sizeof (pre[0]);
 
     struct node* root = constructTree(pre, size);
 
     printf ( "Inorder traversal of the constructed tree: \n" );
     printInorder(root);
 
     return 0;
}

Java

// Java program to construct BST from given preorder
// traversal
 
// A binary tree node
class Node
{
 
     int data;
     Node left, right;
 
     Node( int d)
     {
         data = d;
         left = right = null ;
     }
}
 
class Index
{
 
     int index = 0 ;
}
 
class BinaryTree
{
 
     Index index = new Index();
 
     // A recursive function to construct Full from pre[].
     // preIndex is used to keep track of index in pre[].
     Node constructTreeUtil( int pre[], Index preIndex, int low, int high, int size)
     {
 
         // Base case
         if (preIndex.index >= size || low > high)
         {
             return null ;
         }
 
         // The first node in preorder traversal is root. So
         // take the node at preIndex from pre[] and make it
         // root, and increment preIndex
         Node root = new Node(pre[preIndex.index]);
         preIndex.index = preIndex.index + 1 ;
 
         // If the current subarry has only one element, no
         // need to recur
         if (low == high)
         {
             return root;
         }
 
         // Search for the first element greater than root
         int i;
         for (i = low; i <= high; ++i)
         {
             if (pre[i] > root.data)
             {
                 break ;
             }
         }
 
         // Use the index of element found in preorder to
         // divide preorder array in two parts. Left subtree
         // and right subtree
         root.left = constructTreeUtil(
             pre, preIndex, preIndex.index, i - 1 , size);
         root.right = constructTreeUtil(pre, preIndex, i, high, size);
 
         return root;
     }
 
     // The main function to construct BST from given
     // preorder traversal. This function mainly uses
     // constructTreeUtil()
     Node constructTree( int pre[], int size)
     {
         return constructTreeUtil(pre, index, 0 , size - 1 , size);
     }
 
     // A utility function to print inorder traversal of a
     // Binary Tree
     void printInorder(Node node)
     {
         if (node == null )
         {
             return ;
         }
         printInorder(node.left);
         System.out.print(node.data + " " );
         printInorder(node.right);
     }
 
     // Driver code
     public static void main(String[] args)
     {
         BinaryTree tree = new BinaryTree();
         int pre[] = new int [] { 10 , 5 , 1 , 7 , 40 , 50 };
         int size = pre.length;
         Node root = tree.constructTree(pre, size);
         System.out.println(
             "Inorder traversal of the constructed tree is " );
         tree.printInorder(root);
     }
}
 
// This code has been contributed by Mayank Jaiswal

python

# A O(n^2) Python3 program for construction of BST from preorder traversal
 
# A binary tree node
 
 
class Node():
 
     # A constructor to create a new node
     def __init__( self , data):
         self .data = data
         self .left = None
         self .right = None
 
 
# constructTreeUtil.preIndex is a static variable of
# function constructTreeUtil
 
# Function to get the value of static variable
# constructTreeUtil.preIndex
def getPreIndex():
     return constructTreeUtil.preIndex
 
# Function to increment the value of static variable
# constructTreeUtil.preIndex
 
 
def incrementPreIndex():
     constructTreeUtil.preIndex + = 1
 
# A recurseive function to construct Full from pre[].
# preIndex is used to keep track of index in pre[[].
 
 
def constructTreeUtil(pre, low, high, size):
 
     # Base Case
     if (getPreIndex() > = size or low > high):
         return None
 
     # The first node in preorder traversal is root. So take
     # the node at preIndex from pre[] and make it root, # and increment preIndex
     root = Node(pre[getPreIndex()])
     incrementPreIndex()
 
     # If the current subarray has onlye one element, # no need to recur
     if low = = high:
         return root
 
     # Search for the first element greater than root
     for i in range (low, high + 1 ):
         if (pre[i] > root.data):
             break
 
     # Use the index of element found in preorder to divide
     # preorder array in two parts. Left subtree and right
     # subtree
     root.left = constructTreeUtil(pre, getPreIndex(), i - 1 , size)
 
     root.right = constructTreeUtil(pre, i, high, size)
 
     return root
 
# The main function to construct BST from given preorder
# traversal. This function mailny uses constructTreeUtil()
 
 
def constructTree(pre):
     size = len (pre)
     constructTreeUtil.preIndex = 0
     return constructTreeUtil(pre, 0 , size - 1 , size)
 
 
def printInorder(root):
     if root is None :
         return
     printInorder(root.left)
     print root.data, printInorder(root.right)
 
 
# Driver code
pre = [ 10 , 5 , 1 , 7 , 40 , 50 ]
 
root = constructTree(pre)
print "Inorder traversal of the constructed tree:"
printInorder(root)
 
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

C#

using System;
 
// C# program to construct BST from given preorder traversal
 
// A binary tree node
public class Node
{
 
     public int data;
     public Node left, right;
 
     public Node( int d)
     {
         data = d;
         left = right = null ;
     }
}
 
public class Index
{
 
     public int index = 0;
}
 
public class BinaryTree
{
 
     public Index index = new Index();
 
     // A recursive function to construct Full from pre[].
     // preIndex is used to keep track of index in pre[].
     public virtual Node constructTreeUtil( int [] pre, Index preIndex, int low, int high, int size)
     {
 
         // Base case
         if (preIndex.index >= size || low > high)
         {
             return null ;
         }
 
         // The first node in preorder traversal is root. So
         // take the node at preIndex from pre[] and make it
         // root, and increment preIndex
         Node root = new Node(pre[preIndex.index]);
         preIndex.index = preIndex.index + 1;
 
         // If the current subarry has only one element, no
         // need to recur
         if (low == high)
         {
             return root;
         }
 
         // Search for the first element greater than root
         int i;
         for (i = low; i <= high; ++i)
         {
             if (pre[i] > root.data)
             {
                 break ;
             }
         }
 
         // Use the index of element found in preorder to
         // divide preorder array in two parts. Left subtree
         // and right subtree
         root.left = constructTreeUtil(
             pre, preIndex, preIndex.index, i - 1, size);
         root.right = constructTreeUtil(pre, preIndex, i, high, size);
 
         return root;
     }
 
     // The main function to construct BST from given
     // preorder traversal. This function mainly uses
     // constructTreeUtil()
     public virtual Node constructTree( int [] pre, int size)
     {
         return constructTreeUtil(pre, index, 0, size - 1, size);
     }
 
     // A utility function to print inorder traversal of a
     // Binary Tree
     public virtual void printInorder(Node node)
     {
         if (node == null )
         {
             return ;
         }
         printInorder(node.left);
         Console.Write(node.data + " " );
         printInorder(node.right);
     }
 
     // Driver code
     public static void Main( string [] args)
     {
         BinaryTree tree = new BinaryTree();
         int [] pre = new int [] { 10, 5, 1, 7, 40, 50 };
         int size = pre.Length;
         Node root = tree.constructTree(pre, size);
         Console.WriteLine(
             "Inorder traversal of the constructed tree is " );
         tree.printInorder(root);
     }
}
 
// This code is contributed by Shrikant13

输出如下

Inorder traversal of the constructed tree: 
1 5 7 10 40 50

时间复杂度：O(n^2)

方法2(O(n)时间复杂度)

诀窍是为每个节点设置范围{min .. max}。将范围初始化为{INT_MIN .. INT_MAX}。第一个节点肯定在范围内, 因此请创建根节点。要构造左子树, 请将范围设置为{INT_MIN…root-> data}。如果值在{INT_MIN .. root-> data}范围内, 则这些值是左子树的一部分。要构建正确的子树, 请将范围设置为{root-> data..max .. INT_MAX}。

以下是上述想法的实现：

C ++

/* A O(n) program for construction
of BST from preorder traversal */
#include <bits/stdc++.h>
using namespace std;
 
/* A binary tree node has data, pointer to left child
and a pointer to right child */
class node
{
public :
     int data;
     node* left;
     node* right;
};
 
// A utility function to create a node
node* newNode( int data)
{
     node* temp = new node();
 
     temp->data = data;
     temp->left = temp->right = NULL;
 
     return temp;
}
 
// A recursive function to construct
// BST from pre[]. preIndex is used
// to keep track of index in pre[].
node* constructTreeUtil( int pre[], int * preIndex, int key, int min, int max, int size)
{
     // Base case
     if (*preIndex >= size)
         return NULL;
 
     node* root = NULL;
 
     // If current element of pre[] is in range, then
     // only it is part of current subtree
     if (key > min && key < max)
     {
         // Allocate memory for root of this
         // subtree and increment *preIndex
         root = newNode(key);
         *preIndex = *preIndex + 1;
 
         if (*preIndex < size)
         {
             // Construct the subtree under root
             // All nodes which are in range
             // {min .. key} will go in left
             // subtree, and first such node
             // will be root of left subtree.
             root->left = constructTreeUtil(pre, preIndex, pre[*preIndex], min, key, size);
         }
         if (*preIndex < size)
         {
             // All nodes which are in range
             // {key..max} will go in right
             // subtree, and first such node
             // will be root of right subtree.
             root->right = constructTreeUtil(pre, preIndex, pre[*preIndex], key, max, size);
         }
     }
 
     return root;
}
 
// The main function to construct BST
// from given preorder traversal.
// This function mainly uses constructTreeUtil()
node* constructTree( int pre[], int size)
{
     int preIndex = 0;
     return constructTreeUtil(pre, &preIndex, pre[0], INT_MIN, INT_MAX, size);
}
 
// A utility function to print inorder
// traversal of a Binary Tree
void printInorder(node* node)
{
     if (node == NULL)
         return ;
     printInorder(node->left);
     cout << node->data << " " ;
     printInorder(node->right);
}
 
// Driver code
int main()
{
     int pre[] = { 10, 5, 1, 7, 40, 50 };
     int size = sizeof (pre) / sizeof (pre[0]);
 
     // Function call
     node* root = constructTree(pre, size);
 
     cout << "Inorder traversal of the constructed tree: \n" ;
     printInorder(root);
 
     return 0;
}
 
// This is code is contributed by rathbhupendra

C

/* A O(n) program for construction of BST from preorder
  * traversal */
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
 
/* A binary tree node has data, pointer to left child
    and a pointer to right child */
struct node
{
     int data;
     struct node* left;
     struct node* right;
};
 
// A utility function to create a node
struct node* newNode( int data)
{
     struct node* temp
         = ( struct node*) malloc ( sizeof ( struct node));
 
     temp->data = data;
     temp->left = temp->right = NULL;
 
     return temp;
}
 
// A recursive function to construct BST from pre[].
// preIndex is used to keep track of index in pre[].
struct node* constructTreeUtil( int pre[], int * preIndex, int key, int min, int max, int size)
{
     // Base case
     if (*preIndex >= size)
         return NULL;
 
     struct node* root = NULL;
 
     // If current element of pre[] is in range, then
     // only it is part of current subtree
     if (key > min && key < max)
     {
         // Allocate memory for root of this subtree and
         // increment *preIndex
         root = newNode(key);
         *preIndex = *preIndex + 1;
 
         if (*preIndex < size)
         {
             // Construct the subtree under root
             // All nodes which are in range {min .. key}
             // will go in left subtree, and first such node
             // will be root of left subtree.
             root->left = constructTreeUtil(pre, preIndex, pre[*preIndex], min, key, size);
         }
         if (*preIndex < size)
         {
             // All nodes which are in range {key..max} will
             // go in right subtree, and first such node will
             // be root of right subtree.
             root->right = constructTreeUtil(pre, preIndex, pre[*preIndex], key, max, size);
         }
     }
 
     return root;
}
 
// The main function to construct BST from given preorder
// traversal. This function mainly uses constructTreeUtil()
struct node* constructTree( int pre[], int size)
{
     int preIndex = 0;
     return constructTreeUtil(pre, &preIndex, pre[0], INT_MIN, INT_MAX, size);
}
 
// A utility function to print inorder traversal of a Binary
// Tree
void printInorder( struct node* node)
{
     if (node == NULL)
         return ;
     printInorder(node->left);
     printf ( "%d " , node->data);
     printInorder(node->right);
}
 
// Driver code
int main()
{
     int pre[] = { 10, 5, 1, 7, 40, 50 };
     int size = sizeof (pre) / sizeof (pre[0]);
 
     // function call
     struct node* root = constructTree(pre, size);
 
     printf ( "Inorder traversal of the constructed tree: \n" );
     printInorder(root);
 
     return 0;
}

Java

// Java program to construct BST from given preorder
// traversal
 
// A binary tree node
class Node
{
 
     int data;
     Node left, right;
 
     Node( int d)
     {
         data = d;
         left = right = null ;
     }
}
 
class Index
{
 
     int index = 0 ;
}
 
class BinaryTree
{
 
     Index index = new Index();
 
     // A recursive function to construct BST from pre[].
     // preIndex is used to keep track of index in pre[].
     Node constructTreeUtil( int pre[], Index preIndex, int key, int min, int max, int size)
     {
 
         // Base case
         if (preIndex.index >= size)
         {
             return null ;
         }
 
         Node root = null ;
 
         // If current element of pre[] is in range, then
         // only it is part of current subtree
         if (key > min && key < max)
         {
 
             // Allocate memory for root of this
             // subtree and increment *preIndex
             root = new Node(key);
             preIndex.index = preIndex.index + 1 ;
 
             if (preIndex.index < size)
             {
 
                 // Construct the subtree under root
                 // All nodes which are in range {min .. key}
                 // will go in left subtree, and first such
                 // node will be root of left subtree.
                 root.left = constructTreeUtil(
                     pre, preIndex, pre[preIndex.index], min, key, size);
             }
             if (preIndex.index < size)
             {
                 // All nodes which are in range {key..max}
                 // will go in right subtree, and first such
                 // node will be root of right subtree.
                 root.right = constructTreeUtil(
                     pre, preIndex, pre[preIndex.index], key, max, size);
             }
         }
 
         return root;
     }
 
     // The main function to construct BST from given
     // preorder traversal. This function mainly uses
     // constructTreeUtil()
     Node constructTree( int pre[], int size)
     {
         int preIndex = 0 ;
         return constructTreeUtil(pre, index, pre[ 0 ], Integer.MIN_VALUE, Integer.MAX_VALUE, size);
     }
 
     // A utility function to print inorder traversal of a
     // Binary Tree
     void printInorder(Node node)
     {
         if (node == null )
         {
             return ;
         }
         printInorder(node.left);
         System.out.print(node.data + " " );
         printInorder(node.right);
     }
 
     // Driver code
     public static void main(String[] args)
     {
         BinaryTree tree = new BinaryTree();
         int pre[] = new int [] { 10 , 5 , 1 , 7 , 40 , 50 };
         int size = pre.length;
       
         // Function call
         Node root = tree.constructTree(pre, size);
         System.out.println(
             "Inorder traversal of the constructed tree is " );
         tree.printInorder(root);
     }
}
 
// This code has been contributed by Mayank Jaiswal

python

# A O(n) program for construction of BST from preorder traversal
 
INT_MIN = float ( "-infinity" )
INT_MAX = float ( "infinity" )
 
# A Binary tree node
 
 
class Node:
 
     # Constructor to created a new node
     def __init__( self , data):
         self .data = data
         self .left = None
         self .right = None
 
# Methods to get and set the value of static variable
# constructTreeUtil.preIndex for function construcTreeUtil()
 
 
def getPreIndex():
     return constructTreeUtil.preIndex
 
 
def incrementPreIndex():
     constructTreeUtil.preIndex + = 1
 
# A recursive function to construct BST from pre[].
# preIndex is used to keep track of index in pre[]
 
 
def constructTreeUtil(pre, key, mini, maxi, size):
 
     # Base Case
     if (getPreIndex() > = size):
         return None
 
     root = None
 
     # If current element of pre[] is in range, then
     # only it is part of current subtree
     if (key > mini and key < maxi):
 
         # Allocate memory for root of this subtree
         # and increment constructTreeUtil.preIndex
         root = Node(key)
         incrementPreIndex()
 
         if (getPreIndex() < size):
 
             # Construct the subtree under root
             # All nodes which are in range {min.. key} will
             # go in left subtree, and first such node will
             # be root of left subtree
             root.left = constructTreeUtil(pre, pre[getPreIndex()], mini, key, size)
         if (getPreindex() < size):
 
             # All nodes which are in range{key..max} will
             # go to right subtree, and first such node will
             # be root of right subtree
             root.right = constructTreeUtil(pre, pre[getPreIndex()], key, maxi, size)
 
     return root
 
# This is the main function to construct BST from given
# preorder traversal. This function mainly uses
# constructTreeUtil()
 
 
def constructTree(pre):
     constructTreeUtil.preIndex = 0
     size = len (pre)
     return constructTreeUtil(pre, pre[ 0 ], INT_MIN, INT_MAX, size)
 
 
# A utility function to print inorder traversal of Binary Tree
def printInorder(node):
 
     if node is None :
         return
     printInorder(node.left)
     print node.data, printInorder(node.right)
 
 
# Driver code
pre = [ 10 , 5 , 1 , 7 , 40 , 50 ]
 
# Function call
root = constructTree(pre)
 
print "Inorder traversal of the constructed tree: "
printInorder(root)
 
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

C#

// C# program to construct BST from given preorder traversal
using System;
 
// A binary tree node
public class Node
{
 
     public int data;
     public Node left, right;
 
     public Node( int d)
     {
         data = d;
         left = right = null ;
     }
}
 
public class Index
{
     public int index = 0;
}
 
public class BinaryTree
{
 
     public Index index = new Index();
 
     // A recursive function to construct BST from pre[].
     // preIndex is used to keep track of index in pre[].
     public virtual Node constructTreeUtil( int [] pre, Index preIndex, int key, int min, int max, int size)
     {
 
         // Base case
         if (preIndex.index >= size)
         {
             return null ;
         }
 
         Node root = null ;
 
         // If current element of pre[] is in range, then
         // only it is part of current subtree
         if (key > min && key < max)
         {
 
             // Allocate memory for root of this subtree
             // and increment *preIndex
             root = new Node(key);
             preIndex.index = preIndex.index + 1;
 
             if (preIndex.index < size)
             {
 
                 // Construct the subtree under root
                 // All nodes which are in range
                 // {min .. key} will go in left
                 // subtree, and first such node will
                 // be root of left subtree.
                 root.left = constructTreeUtil(
                     pre, preIndex, pre[preIndex.index], min, key, size);
             }
             if (preIndex.index < size)
             {
                 // All nodes which are in range
                 // {key..max} will go in right
                 // subtree, and first such node
                 // will be root of right subtree.
                 root.right = constructTreeUtil(
                     pre, preIndex, pre[preIndex.index], key, max, size);
             }
         }
 
         return root;
     }
 
     // The main function to construct BST from given
     // preorder traversal. This function mainly uses
     // constructTreeUtil()
     public virtual Node constructTree( int [] pre, int size)
     {
 
         return constructTreeUtil(pre, index, pre[0], int .MinValue, int .MaxValue, size);
     }
 
     // A utility function to print inorder traversal of a
     // Binary Tree
     public virtual void printInorder(Node node)
     {
         if (node == null )
         {
             return ;
         }
         printInorder(node.left);
         Console.Write(node.data + " " );
         printInorder(node.right);
     }
 
     // Driver code
     public static void Main( string [] args)
     {
         BinaryTree tree = new BinaryTree();
         int [] pre = new int [] { 10, 5, 1, 7, 40, 50 };
         int size = pre.Length;
       
         // Function call
         Node root = tree.constructTree(pre, size);
         Console.WriteLine(
             "Inorder traversal of the constructed tree is " );
         tree.printInorder(root);
     }
}
 
// This code is contributed by Shrikant13

输出如下

Inorder traversal of the constructed tree: 
1 5 7 10 40 50

时间复杂度：O(n^2)

我们很快将在另一篇文章中发布O(n)迭代解决方案。

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。