当前位置:网站首页>Leetcode skimming: binary tree 17 (construct binary tree from middle order and post order traversal sequence)
Leetcode skimming: binary tree 17 (construct binary tree from middle order and post order traversal sequence)
2022-07-05 20:03:00 【Taotao can't learn English】
106. Construct binary tree from middle order and post order traversal sequence
According to the middle order traversal and post order traversal of a tree, a binary tree is constructed .
Be careful :
You can assume that there are no duplicate elements in the tree .
for example , give
In the sequence traversal inorder = [9,3,15,20,7]
After the sequence traversal postorder = [9,15,7,20,3]
Return to the following binary tree :
The difficulty is good , Recursive method . The termination condition is The length of both arrays is 0 when , return null . After the sequence traversal Left Right root . Every time the post order traversal is constructed , The last of the subsequent array is always the root node , Then according to this root node , There are also subject regulations No repeating elements , Then find the current root node in the ordered array , Take it as the boundary to divide the middle order array into the middle order array of the left subtree and the middle order array of the right subtree . And in the middle order array Root node The location of , Just put it in the subsequent array , This position is forward yes Postorder traversal of left subtree , This position includes the position backwards until The next to last element Is the postorder traversal of the right subtree , The last one is the root node .
Then take the first of the left subtree 、 Post array and First of right subtree 、 The last array can be recursive .
package com.programmercarl.tree;
/** * @ClassName BuildTree * @Descriotion TODO * @Author nitaotao * @Date 2022/7/5 12:37 * @Version 1.0 * https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/ * 106. Construct binary tree from middle order and post order traversal sequence **/
public class BuildTree {
/** * @param inorder In the sequence traversal 1 2 * @param postorder After the sequence traversal 2 1 * @return */
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (inorder.length == 0 && postorder.length == 0) {
return null;
}
// The length of the last array is equal , Because the number of elements is the same
// The first element of post order traversal is the root node
TreeNode root = new TreeNode(postorder[postorder.length - 1]);
// Find the root node in the middle order traversal
int rootIndex = 0;
for (int i = 0; i < inorder.length; i++) {
if (root.val == inorder[i]) {
rootIndex = i;
}
}
// The medium order array is divided into left subtree and right subtree
int[] leftIn = new int[rootIndex];
int[] rightIn = new int[inorder.length - rootIndex - 1];
for (int i = 0; i < inorder.length; i++) {
if (i < rootIndex) {
leftIn[i] = inorder[i];
} else if (i > rootIndex) {
rightIn[i-rootIndex-1] = inorder[i];
}
}
// After order traversal array front rootIndex Bit is left subtree , after rootIndex Bit is a right subtree
int[] leftPost = new int[rootIndex];
int[] rightPost = new int[inorder.length - rootIndex - 1];
// The last node , It has been built as the root node .
for (int i = 0; i < postorder.length - 1; i++) {
if (i < rootIndex) {
leftPost[i] = postorder[i];
} else {
rightPost[i - rootIndex] = postorder[i];
}
}
// Construct left and right subtrees
root.left = buildTree(leftIn, leftPost);
root.right = buildTree(rightIn, rightPost);
return root;
}
public static void main(String[] args) {
new BuildTree().buildTree(new int[]{
1, 2}, new int[]{
2, 1});
}
}
边栏推荐
- Go language | 01 wsl+vscode environment construction pit avoidance Guide
- C langue OJ obtenir PE, ACM démarrer OJ
- selenium 元素信息
- Analysis of openh264 decoded data flow
- Debezium series: modify the source code to support drop foreign key if exists FK
- JS implementation prohibits web page zooming (ctrl+ mouse, +, - zooming effective pro test)
- MySql的root密码忘记该怎么找回
- 《乔布斯传》英文原著重点词汇笔记(十二)【 chapter ten & eleven】
- 解决php无法将string转换为json的办法
- S7-200smart uses V90 Modbus communication control library to control the specific methods and steps of V90 servo
猜你喜欢
[OBS] qstring's UTF-8 Chinese conversion to blog printing UTF-8 char*
[untitled]
Zhongang Mining: analysis of the current market supply situation of the global fluorite industry in 2022
618 "low key" curtain call, how can baiqiushangmei join hands with the brand to cross the "uncertain era"?
解决Thinkphp框架应用目录下数据库配置信息修改后依然按默认方式连接
Complete interview questions for interviewers and senior Android engineers in front-line Internet enterprises
- Oui. Net Distributed Transaction and Landing Solution
leetcode刷题:二叉树10(完全二叉树的节点个数)
leetcode刷题:二叉树17(从中序与后序遍历序列构造二叉树)
Hong Kong stocks will welcome the "best ten yuan store". Can famous creative products break through through the IPO?
随机推荐
Four methods of random number generation | random | math | threadlocalrandom | securityrandom
Leetcode brush question: binary tree 14 (sum of left leaves)
leetcode刷题:二叉树12(二叉树的所有路径)
Is it safe for CICC fortune to open an account online?
港股将迎“最牛十元店“,名创优品能借IPO突围?
Debezium series: modify the source code to support UNIX_ timestamp() as DEFAULT value
Is it safe for Anxin securities to open an account online?
深度學習 卷積神經網絡(CNN)基礎
[FAQ] summary of common causes and solutions of Huawei account service error 907135701
How to select the Block Editor? Impression notes verse, notation, flowus
Zero cloud new UI design
leetcode刷题:二叉树11(平衡二叉树)
Where is the operation of new bonds? Is it safer and more reliable to open an account
DP: tree DP
ICTCLAS word Lucene 4.9 binding
Recommended collection, my Tencent Android interview experience sharing
CADD课程学习(7)-- 模拟靶点和小分子相互作用 (半柔性对接 AutoDock)
webuploader文件上传 拖拽上传 进度监听 类型控制 上传结果监听控件
Float.floatToRawIntBits的返回值具体意思,将float转为byte数组
Debezium series: record the messages parsed by debezium and the solutions after the MariaDB database deletes multiple temporary tables