<> subject

Input a binary tree preorder traversal and in order traversal results , Please rebuild the binary tree .

be careful :

* The values of each node in the binary tree are different from each other ;
* Input of the preorder traversal and in order traversal must be legal ;
Examples
given : Preorder traversal is :[3, 9, 20, 15, 7] Middle order traversal is :[9, 3, 15, 20, 7] return :[3, 9, 20, null, null,
15, 7, null, null, null, null] The binary tree returned is as follows : 3 / \ 9 20 / \ 15 7
<> thinking

( recursion ) O ( n ) O(n) O(n)

Recursive establishment of the whole binary tree : First, create left and right subtrees recursively , Then create the root node , And let the pointer point to two subtrees .

The specific steps are as follows :

* Using preorder traversal first Find root node : The first number of preorder traversal , Is the value of the root node ;
* Find the location of the root node in the middle order traversal k, be k On the left is the middle order traversal of the left subtree , On the right is the middle order traversal of the right subtree ;
* Suppose that the length of the middle order traversal of the left subtree is l, In preorder traversal , After the root node l number , Is the preorder traversal of the left subtree , The remaining number is the preorder traversal of the right subtree ;
* With the pre order traversal and middle order traversal of the left and right subtrees , We can create left and right subtrees recursively , Then create the root node ;
Time complexity analysis

When we initialize , Using hash table (unordered_map<int,int>
) Record the position of each value in the middle traversal , So when we recurs to each node , The operation of finding the root node position in middle order traversal , It only needs O ( 1 ) O(1) O(1)
Time of day . here , How long does it take to create each node O ( 1 ) O(1) O(1), So the total time complexity is O ( n ) O(n) O(n).

<> code
/** * Definition for a binary tree node. * struct TreeNode { * int val; *
TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL),
right(NULL) {} * }; */ class Solution { public: unordered_map<int,int> pos;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { int n =
preorder.size(); for (int i = 0; i < n; i ++ ) pos[inorder[i]] = i;
// Record the location of the root node return dfs(preorder, inorder, 0, n - 1, 0, n - 1);
// Creating left and right subtrees recursively , Finally, point the root node to the left and right subtrees } TreeNode* dfs(vector<int>&pre, vector<int>&in, int pl,
int pr, int il, int ir) { if (pl > pr) return NULL; // If the left interval is larger than the right interval , Direct return NULL int k =
pos[pre[pl]] - il; // The length of preorder traversal interval TreeNode* root = new TreeNode(pre[pl]);// Create root node
root->left = dfs(pre, in, pl + 1, pl + k, il, il + k - 1); // Preorder and middle order traversal intervals of left subtree root-
>right = dfs(pre, in, pl + k + 1, pr, il + k + 1, ir);// Preorder and middle order traversal intervals of right subtree return
root; } };

Technology
©2019-2020 Toolsou All rights reserved,
Solve in servlet The Chinese output in is a question mark C String function and character function in language MySQL management 35 A small coup optimization Java performance —— Concise article Seven sorting algorithms (java code ) use Ansible Batch deployment SSH Password free login to remote host according to excel generate create Build table SQL sentence Spring Source code series ( sixteen )Spring merge BeanDefinition Principle of Virtual machine installation Linux course What are the common exception classes ?