当前位置:网站首页>Recursive method constructs binary tree from middle order and post order traversal sequence
Recursive method constructs binary tree from middle order and post order traversal sequence
2022-07-07 08:04:00 【Hydrion-Qlz】
106. Construct binary tree from middle order and post order traversal sequence
Medium difficulty
Given two arrays of integers inorder
and postorder
, among inorder
Is the middle order traversal of a binary tree , postorder
Is the post order traversal of the same tree , Please construct and return this Binary tree .
Ideas
The knowledge points that need to be understood are :
- In the middle order traversal, the left side of a node is all nodes of its left subtree , On the right are all the nodes of its right subtree
- The last one in the subsequent traversal is the current node , Its left subtree and right subtree are on its left
We can find the current node according to the subsequent traversal , Then find the position of the current root node in the ordered array , Then the range of the new left subtree and right subtree is determined by the position of the root node and the range of its subtree , Then recurs continuously , Until the last traversal of the entire array .
We cannot determine the range of left subtree and right subtree in subsequent traversal , But you can get this value from the middle order traversal
Specific please see 37 And 38 That's ok
package cn.edu.xjtu.carlWay.tree.postAndInConstructBinaryTree;
import cn.edu.xjtu.Util.TreeNode.TreeNode;
/** * 106. Construct binary tree from middle order and post order traversal sequence * Given two arrays of integers inorder and postorder , among inorder Is the middle order traversal of a binary tree , postorder Is the post order traversal of the same tree , Please construct and return this Binary tree . * <p> * https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/ */
public class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
return helpBuild(inorder, 0, inorder.length, postorder, 0, postorder.length);
}
private TreeNode helpBuild(int[] inorder, int inLeft, int inRight, int[] postorder, int postLeft, int postRight) {
// There are no elements
if (inRight - inLeft < 1) {
return null;
}
// There's only one element
if (inRight - inLeft == 1) {
return new TreeNode(inorder[inLeft]);
}
// The last element in the subsequent array is the root node
int rootVal = postorder[postRight - 1];
TreeNode root = new TreeNode(rootVal);
// Find the position of the root node in the ordered array
int rootIndex = 0;
for (int i = inLeft; i < inRight; i++) {
if (inorder[i] == rootVal) {
rootIndex = i;
break;
}
}
root.left = helpBuild(inorder, inLeft, rootIndex, postorder, postLeft, postLeft + (rootIndex - inLeft));
root.right = helpBuild(inorder, rootIndex + 1, inRight, postorder, postLeft + (rootIndex - inLeft), postRight - 1);
return root;
}
}
边栏推荐
- [Matlab] Simulink 自定义函数中的矩阵乘法工作不正常时可以使用模块库中的矩阵乘法模块代替
- The charm of SQL optimization! From 30248s to 0.001s
- Quickly use Jacobo code coverage statistics
- Button wizard collection learning - mineral medicine collection and running map
- The principle and implementation of buffer playback of large video files
- A bit of knowledge - about Apple Certified MFI
- 【数字IC验证快速入门】15、SystemVerilog学习之基本语法2(操作符、类型转换、循环、Task/Function...内含实践练习)
- 【数字IC验证快速入门】13、SystemVerilog interface 和 program 学习
- Leetcode 40: combined sum II
- Problem solving: unable to connect to redis
猜你喜欢
Shell 脚本的替换功能实现
SQL优化的魅力!从 30248s 到 0.001s
Qt学习27 应用程序中的主窗口
You Li takes you to talk about C language 6 (common keywords)
Visualization Document Feb 12 16:42
JSON data flattening pd json_ normalize
[CV] Wu Enda machine learning course notes | Chapter 8
Niu Mei's mathematical problem --- combinatorial number
自定义类加载器加载网络Class
[2022 actf] Web Topic recurrence
随机推荐
解决问题:Unable to connect to Redis
【数字IC验证快速入门】10、Verilog RTL设计必会的FIFO
[mathematical notes] radian
【数字IC验证快速入门】14、SystemVerilog学习之基本语法1(数组、队列、结构体、枚举、字符串...内含实践练习)
Problem solving: unable to connect to redis
2022制冷与空调设备运行操作复训题库及答案
自定义类加载器加载网络Class
Paddlepaddle 29 dynamically modify the network structure without model definition code (relu changes to prelu, conv2d changes to conv3d, 2D semantic segmentation model changes to 3D semantic segmentat
太真实了,原来自己一直没有富裕起来是有原因的
CTF daily question day43 rsa5
Linux server development, MySQL process control statement
探索Cassandra的去中心化分布式架构
Padavan manually installs PHP
Téléchargement des données de conception des puces
[UVM practice] Chapter 1: configuring the UVM environment (taking VCs as an example), run through the examples in the book
C language communication travel card background system
[Stanford Jiwang cs144 project] lab3: tcpsender
Bugku CTF daily one question chessboard with only black chess
Numbers that appear only once
[UVM foundation] what is transaction