<> 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,
Huawei 2021 session Hardware Engineer Logical post (FPGA) Super detailed surface !!!Vue-element-admin upgrade ui edition virtual machine VMware Download and install the most detailed tutorial !C++ Move constructor and copy constructor sound of dripping water java Backstage interview pygame Realize full screen mode and adjustable window size mysql Database setting character set configuration modification my.ini file (windows)30 What's the experience of being a junior programmer at the age of 20 C++ Multithreading programming ( Summary of common functions and parameters )python_ cherry tree