当前位置:网站首页>Leetcode problem solving - 889 Construct binary tree according to preorder and postorder traversal
Leetcode problem solving - 889 Construct binary tree according to preorder and postorder traversal
2022-07-06 23:24:00 【100-1 = 0】
private int[] pre
private int[] post;
public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
pre = preorder;
post = postorder;
return buildTree(0,0,pre.length);
}
private TreeNode buildTree(int i,int j,int n){
if (n==0) return null;
TreeNode root = new TreeNode(pre[i++]);
if (n==1) return root;
int L = 1;
for (;L<n;L++) if (post[j+L-1]==pre[i]) break;
root.left = buildTree(i,j,L);
root.right = buildTree(i+L,j+L,n-1-L);
return root;
}
Ideas :
The first thing to know is
The former sequence traversal
[ The root node ,( The left subtree ),( Right subtree )]
After the sequence traversal
[( The left subtree ),( Right subtree ), The root node ]
that , We can know that the root node is the first element in the preorder traversal , So how to divide the left and right subtrees ? If we know the length of the left subtree, can we divide the left and right subtrees ? How to get the length ?
Where will the root node of the left subtree in the pre order traversal appear in the left subtree in the post order traversal ?
The answer is : the last one
That is to say :pre[1]==post[L-1]
set up i Traverse the first element index of the left subtree for the previous order ,j Traverse the index of the first element of the left subtree for the post order , Yes pre[i]=post[j+L-1]
Thus, the left and right subtrees can be divided for the next recursion
- take preorder and postorder Member variables stored in the class , It reduces the cumbersome process of transferring parameters
- At the beginning , The index of the first element of the pre order traversal of the left subtree is 1, But the answer is 0, This is because you need to create the root node first , After creating i It's going to increase 1, The index of the first element of the left subtree traversed by the latter order is 0, That is to say, it's passed on 0, And passed the length of the subtree node
- If the subtree length is 0, Go straight back to null, by 1, Then create the root node and return , Longer than 1, Continue to divide the left and right subtrees
- Loop to get the length of the left subtree , Continue to recursively create left and right subtrees
- return root
边栏推荐
- Thinkphp5 multi table associative query method join queries two database tables, and the query results are spliced and returned
- Huawei cloud gaussdb (for redis) unveils issue 21: using Gauss redis to achieve secondary indexing
- Motion capture for snake motion analysis and snake robot development
- Dayu200 experience officer runs the intelligent drying system page based on arkui ETS on dayu200
- What can be done for traffic safety?
- Koa2 addition, deletion, modification and query of JSON array
- Example code of MySQL split string as query condition
- 浅谈现在的弊端与未来的发展
- Dayu200 experience officer homepage AITO video & Canvas drawing dashboard (ETS)
- Cover fake big empty talk in robot material sorting
猜你喜欢
Les entreprises ne veulent pas remplacer un système vieux de dix ans
室内LED显示屏应该怎么选择?这5点注意事项必须考虑在内
docker启动mysql及-eMYSQL_ROOT_PASSWORD=my-secret-pw问题解决
What can be done for traffic safety?
案例推荐丨安擎携手伙伴,保障“智慧法院”更加高效
Dayu200 experience officer homepage AITO video & Canvas drawing dashboard (ETS)
CUDA exploration
Coscon'22 community convening order is coming! Open the world, invite all communities to embrace open source and open a new world~
Flutter life cycle
Thinkphp5 multi table associative query method join queries two database tables, and the query results are spliced and returned
随机推荐
Isomorphism + cross end, knowing applet +kbone+finclip is enough!
What does front-end processor mean? What is the main function? What is the difference with fortress machine?
[unity] upgraded version · Excel data analysis, automatically create corresponding C classes, automatically create scriptableobject generation classes, and automatically serialize asset files
mysql-cdc 的jar包 ,在flink运行模式下,是不是要放在不同的地方呢?
Devsecops software R & D security practice - release
C three ways to realize socket data reception
Stop saying that microservices can solve all problems
Summary of three methods for MySQL to view table structure
CUDA exploration
Efficient ETL Testing
室内LED显示屏应该怎么选择?这5点注意事项必须考虑在内
docker mysql5.7如何设置不区分大小写
Case recommendation: An Qing works with partners to ensure that the "smart court" is more efficient
Les entreprises ne veulent pas remplacer un système vieux de dix ans
DR-Net: dual-rotation network with feature map enhancement for medical image segmentation
How to choose the server system
JS addition, deletion, modification and query of JSON array
(1) Chang'an chain learning notes - start Chang'an chain
On file uploading of network security
Coscon'22 community convening order is coming! Open the world, invite all communities to embrace open source and open a new world~