本文概述
例如, 如果给定的遍历为{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 rathbhupendraC
/* 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 Jaiswalpython
# 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 rathbhupendraC
/* 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 Jaiswalpython
# 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)迭代解决方案。
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。
![从字法上最小长度N的排列，使得对于正好为K个索引，a[i] a[i]+1](https://www.lsbin.com/wp-content/themes/begin%20lts/img/loading.png)
