当前位置:网站首页>leetcode:105. Constructing binary trees from preorder and inorder traversal sequences
leetcode:105. Constructing binary trees from preorder and inorder traversal sequences
2022-07-07 07:39:00 【uncle_ ll】
105. Construction of binary trees from traversal sequences of preorder and middle order
source : Power button (LeetCode)
link : https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
Given two arrays of integers preorder and inorder , among preorder Is the prior traversal of a binary tree , inorder Is the middle order traversal of the same tree , Please construct a binary tree and return its root node .
Example 1:
Input : preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output : [3,9,20,null,null,15,7]
Example 2:
Input : preorder = [-1], inorder = [-1]
Output : [-1]
Tips :
- 1 <= preorder.length <= 3000
- inorder.length == preorder.length
- -3000 <= preorder[i], inorder[i] <= 3000
- preorder and inorder all No repetition Elements
- inorder All appear in preorder
- preorder Guarantee It is the preorder traversal sequence of binary tree
- inorder Guarantee It is the middle order traversal sequence of binary tree
solution
- recursive : Pre order traversal and middle order traversal are given , The first element of the preorder traversal is the root node location , Then, based on the value of the root node, go to the middle order traversal to find the location of the root node , Based on this, the middle order traversal is divided into left subtree traversal and right subtree traversal results ; Find the preorder traversal of left and right subtrees in the preorder traversal based on the length of left subtree ; Next, you can recursively traverse the pre order and middle order of the left subtree , Preorder traversal and inorder traversal of right subtree ; obtain root.left And root.right, Eventually return root that will do ; The key is to find root The subscript ; If using index Way to find words , Each search requires a traversal , The complexity is O ( n ) O(n) O(n), The total complexity is O ( n 2 ) O(n^2) O(n2), Here, a hash table is used to store the subscript of the middle order traversal , Find time changed to O ( 1 ) O(1) O(1), Space for time
Code implementation
recursive
python Realization
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
n = len(preorder)
if n == 0:
return None
indexs = {
element: i for i, element in enumerate(inorder)}
def helper(preorder_left, preorder_right, inorder_left, inorder_right):
if preorder_left > preorder_right:
return None
preorder_index = preorder_left
inorder_root = indexs[preorder[preorder_index]]
root = TreeNode(preorder[preorder_index])
left_preorder_size = inorder_root - inorder_left
root.left = helper(1+preorder_left, preorder_left+left_preorder_size, inorder_left, inorder_root-1)
root.right = helper(1+preorder_left+left_preorder_size, preorder_right, inorder_root+1, inorder_right)
return root
return helper(0, n-1, 0, n-1)
c++ Realization
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class Solution {
private:
unordered_map<int, int> index;
public:
TreeNode* helper(const vector<int>& preorder, const vector<int>& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
if (preorder_left > preorder_right)
return nullptr;
int preorder_root = preorder_left;
int inorder_root = index[preorder[preorder_root]];
TreeNode* root = new TreeNode(preorder[preorder_root]);
int size_left_subtree = inorder_root - inorder_left;
root->left = helper(preorder, inorder, preorder_left+1, preorder_left+size_left_subtree, inorder_left, inorder_root-1);
root->right = helper(preorder, inorder, preorder_left+size_left_subtree+1, preorder_right, inorder_root+1, inorder_right);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = preorder.size();
if (n == 0)
return nullptr;
for (int i=0; i<n; i++) {
index[inorder[i]] = i;
}
return helper(preorder, inorder, 0, n-1, 0, n-1);
}
};
Complexity analysis
- Time complexity : O ( N ) O(N) O(N)
- Spatial complexity : O ( N ) O(N) O(N)
边栏推荐
- Talk about seven ways to realize asynchronous programming
- KBU1510-ASEMI电源专用15A整流桥KBU1510
- vus.SSR在asynData函数中请求数据的注意事项
- Deep learning Flower Book + machine learning watermelon book electronic version I found
- 按键精灵采集学习-矿药采集及跑图
- Initial experience of teambiion network disk (Alibaba cloud network disk)
- 外包干了三年,废了...
- "Xiaodeng in operation and maintenance" meets the compliance requirements of gdpr
- JS small exercise
- Leetcode-226. Invert Binary Tree
猜你喜欢
95后CV工程师晒出工资单,狠补了这个,真香...
外包干了三年,废了...
How to reduce inventory with high concurrency on the Internet
"Xiaodeng in operation and maintenance" meets the compliance requirements of gdpr
【Liunx】进程控制和父子进程
1142_ SiCp learning notes_ Functions and processes created by functions_ Linear recursion and iteration
身边35岁程序员如何建立起技术护城河?
《动手学深度学习》(四) -- 卷积神经网络 CNN
Dynamics CRM server deployment - restore database prompt: the database is in use
Detailed explanation of neo4j installation process
随机推荐
Several important steps to light up the display
深度学习花书+机器学习西瓜书电子版我找到了
Advanced level of C language (high level) pointer
Lm11 reconstruction of K-line and construction of timing trading strategy
JS decorator @decorator learning notes
直播平台源码,可折叠式菜单栏
JS small exercise
Leetcode-226. Invert Binary Tree
4、 High performance go language release optimization and landing practice youth training camp notes
【性能压测】如何做好性能压测?
Music | cat and mouse -- classic not only plot
Six methods of flattening arrays with JS
1142_ SiCp learning notes_ Functions and processes created by functions_ Linear recursion and iteration
Build personal website based on flask
Project practice five fitting straight lines to obtain the center line
Mutual conversion between InputStream, int, shot, long and byte arrays
07_ Handout on the essence and practical skills of text measurement and geometric transformation
Robot technology innovation and practice old version outline
gslx680触摸屏驱动源码码分析(gslX680.c)
Software acceptance test