给定二叉树的按序和按级遍历，构造二叉树。下面是一个例子来说明这个问题。
null
例如：
Input: Two arrays that represent Inorder and level order traversals of a Binary Treein[] = {4, 8, 10, 12, 14, 20, 22};level[] = {20, 8, 22, 4, 12, 10, 14};Output: Construct the tree represented by the two arrays. For the above two arrays, the constructed tree is shown.
![图片[1]-从有序和水平有序遍历|集2构造一棵树-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_BinaryTree4-300x258.png)
我们在下面的帖子中讨论了一个在O（N^3）中有效的解决方案 从有序和水平有序遍历|集1构造一棵树
方法： 下面的算法使用O（N^2）时间复杂度来解决上述问题 无序集 C++中的数据结构（基本上是一个哈希表）将当前根的左子树的值放在后面，我们将检查O（1）的复杂度，以查找当前的级别顺序节点是否是左子树的一部分。 如果它是左子树的一部分，则为左子树添加一个lLevel数组，否则将其添加到右子树的lLevel数组。
下面是上述想法的实现
C++
/* program to construct tree using inorder and levelorder traversals */ #include <bits/stdc++.h> using namespace std; /* A binary tree node */ struct Node { int key; struct Node* left, *right; }; Node* makeNode( int data){ Node* newNode = new Node(); newNode->key = data; newNode->right = newNode->right = NULL; return newNode; } // Function to build tree from given // levelorder and inorder Node* buildTree( int inorder[], int levelOrder[], int iStart, int iEnd, int n) { if (n <= 0) return NULL; // First node of level order is root Node* root = makeNode(levelOrder[0]); // Search root in inorder int index = -1; for ( int i=iStart; i<=iEnd; i++){ if (levelOrder[0] == inorder[i]){ index = i; break ; } } // Insert all left nodes in hash table unordered_set< int > s; for ( int i=iStart;i<index;i++) s.insert(inorder[i]); // Separate level order traversals // of left and right subtrees. int lLevel[s.size()]; // Left int rLevel[iEnd-iStart-s.size()]; // Right int li = 0, ri = 0; for ( int i=1;i<n;i++) { if (s.find(levelOrder[i]) != s.end()) lLevel[li++] = levelOrder[i]; else rLevel[ri++] = levelOrder[i]; } // Recursively build left and right // subtrees and return root. root->left = buildTree(inorder, lLevel, iStart, index-1, index-iStart); root->right = buildTree(inorder, rLevel, index+1, iEnd, iEnd-index); return root; } /* Utility function to print inorder traversal of binary tree */ void printInorder(Node* node) { if (node == NULL) return ; printInorder(node->left); cout << node->key << " " ; printInorder(node->right); } // Driver Code int main() { int in[] = {4, 8, 10, 12, 14, 20, 22}; int level[] = {20, 8, 22, 4, 12, 10, 14}; int n = sizeof (in)/ sizeof (in[0]); Node *root = buildTree(in, level, 0, n - 1, n); /* Let us test the built tree by printing Inorder traversal */ cout << "Inorder traversal of the " "constructed tree is " ; printInorder(root); return 0; } |
JAVA
/* * program to construct tree using inorder * and levelorder traversals */ import java.util.HashSet; class GFG { /* A binary tree node */ static class Node { int key; Node left, right; }; static Node makeNode( int data) { Node newNode = new Node(); newNode.key = data; newNode.right = newNode.right = null ; return newNode; } // Function to build tree from given // levelorder and inorder static Node buildTree( int inorder[], int levelOrder[], int iStart, int iEnd, int n) { if (n <= 0 ) return null ; // First node of level order is root Node root = makeNode(levelOrder[ 0 ]); // Search root in inorder int index = - 1 ; for ( int i = iStart; i <= iEnd; i++) { if (levelOrder[ 0 ] == inorder[i]) { index = i; break ; } } // Insert all left nodes in hash table HashSet<Integer> s = new HashSet<>(); for ( int i = iStart; i < index; i++) s.add(inorder[i]); // Separate level order traversals // of left and right subtrees. int [] lLevel = new int [s.size()]; // Left int [] rLevel = new int [iEnd - iStart - s.size()]; // Right int li = 0 , ri = 0 ; for ( int i = 1 ; i < n; i++) { if (s.contains(levelOrder[i])) lLevel[li++] = levelOrder[i]; else rLevel[ri++] = levelOrder[i]; } // Recursively build left and right // subtrees and return root. root.left = buildTree(inorder, lLevel, iStart, index - 1 , index - iStart); root.right = buildTree(inorder, rLevel, index + 1 , iEnd, iEnd - index); return root; } /* * Utility function to print inorder * traversal of binary tree */ static void printInorder(Node node) { if (node == null ) return ; printInorder(node.left); System.out.print(node.key + " " ); printInorder(node.right); } // Driver Code public static void main(String[] args) { int in[] = { 4 , 8 , 10 , 12 , 14 , 20 , 22 }; int level[] = { 20 , 8 , 22 , 4 , 12 , 10 , 14 }; int n = in.length; Node root = buildTree(in, level, 0 , n - 1 , n); /* * Let us test the built tree by * printing Inorder traversal */ System.out.println( "Inorder traversal of the constructed tree is " ); printInorder(root); } } // This code is contributed by sanjeev2552 |
Javascript
<script> /* program to construct tree using inorder and levelorder traversals */ /* A binary tree node */ class Node { constructor(data) { this .left = null ; this .right = null ; this .key = data; } } function makeNode(data) { let newNode = new Node(data); return newNode; } // Function to build tree from given // levelorder and inorder function buildTree(inorder, levelOrder, iStart, iEnd, n) { if (n <= 0) return null ; // First node of level order is root let root = makeNode(levelOrder[0]); // Search root in inorder let index = -1; for (let i = iStart; i <= iEnd; i++) { if (levelOrder[0] == inorder[i]) { index = i; break ; } } // Insert all left nodes in hash table let s = new Set(); for (let i = iStart; i < index; i++) s.add(inorder[i]); // Separate level order traversals // of left and right subtrees. let lLevel = new Array(s.size); // Left let rLevel = new Array(iEnd - iStart - s.size); // Right let li = 0, ri = 0; for (let i = 1; i < n; i++) { if (s.has(levelOrder[i])) lLevel[li++] = levelOrder[i]; else rLevel[ri++] = levelOrder[i]; } // Recursively build left and right // subtrees and return root. root.left = buildTree(inorder, lLevel, iStart, index - 1, index - iStart); root.right = buildTree(inorder, rLevel, index + 1, iEnd, iEnd - index); return root; } /* * Utility function to print inorder * traversal of binary tree */ function printInorder(node) { if (node == null ) return ; printInorder(node.left); document.write(node.key + " " ); printInorder(node.right); } let In = [ 4, 8, 10, 12, 14, 20, 22 ]; let level = [ 20, 8, 22, 4, 12, 10, 14 ]; let n = In.length; let root = buildTree(In, level, 0, n - 1, n); /* * Let us test the built tree by * printing Inorder traversal */ document.write( "Inorder traversal of the constructed tree is " + "</br>" ); printInorder(root); </script> |
输出
Inorder traversal of the constructed tree is 4 8 10 12 14 20 22
时间复杂度：O（N^2）
优化： 没有单独的水平顺序遍历左右子树数组。
方法： 使用哈希。
使用 哈希图 存储水平顺序遍历的索引。在从索引开始和结束的范围内，从级别顺序映射中搜索索引最少的元素。递归地创建左子树和右子树。
index -> the least indexfor left subtree: start to index-1for right subtree: index+1 to end
实施：
JAVA
import java.util.HashMap; //class Node class Node{ int data; Node left,right; Node( int data){ this .data = data; left = right = null ; } } public class ConstructTree { //hashmap to store the indices of levelorder array HashMap<Integer,Integer> map = new HashMap<>(); //function to construct hashmap void constructMap( int level[]) { for ( int i= 0 ;i<level.length;i++) map.put(level[i], i); } //function to construct binary tree from inorder and levelorder Node construct( int in[], int level[], int start, int end) { //if start is greater than end return null if (start > end) return null ; int min_index = start; //In the range of start & end from inorder, search the element //with least index from level order map for ( int i=start+ 1 ;i<=end;i++) { int temp = in[i]; //if current element from inorder have least index in //levelorder map, update min_index if (map.get(in[min_index]) > map.get(temp)) min_index = i; } //create a node with current element Node root = new Node(in[min_index]); //if start is equal to end, then return root if (start == end) return root; //construct left and right subtrees root.left = construct(in,level,start,min_index- 1 ); root.right = construct(in,level,min_index+ 1 ,end); return root; } //function to print inorder void printInorder(Node node) { if (node == null ) return ; printInorder(node.left); System.out.print(node.data + " " ); printInorder(node.right); } //Driver function public static void main(String[] args) { ConstructTree tree = new ConstructTree(); int in[] = { 4 , 8 , 10 , 12 , 14 , 20 , 22 }; int level[] = { 20 , 8 , 22 , 4 , 12 , 10 , 14 }; //function calls tree.constructMap(level); int n = level.length; Node root = tree.construct(in, level, 0 , n- 1 ); tree.printInorder(root); } } //This method is contributed by Likhita AVL |
输出
4 8 10 12 14 20 22
时间复杂性： O（n^2）。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
