当前位置:网站首页>Recursive method to construct binary tree from preorder and inorder traversal sequence
Recursive method to construct binary tree from preorder and inorder traversal sequence
2022-07-07 08:04:00 【Hydrion-Qlz】
105. Construction of binary trees from traversal sequences of preorder and middle order
Medium difficulty
Given two arrays of integers preorder
and inorder
, among preorder
It's a binary tree The first sequence traversal , inorder
It's from the same tree In the sequence traversal , Please construct a binary tree and return its root node .
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 first node in the preorder traversal is the current node , Its left subtree and right subtree are on its right
We can find the current node according to the previous 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 the preceding traversal , But you can get this value from the middle order traversal
Specific please see 32 And 33 That's ok
package cn.edu.xjtu.carlWay.tree.preAndInConstructBinaryTree;
import cn.edu.xjtu.Util.TreeNode.TreeNode;
/** * 105. Construction of binary trees from traversal sequences of preorder and middle order * 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 . * <p> * https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/ */
public class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return helpBuild(preorder, 0, preorder.length, inorder, 0, inorder.length);
}
private TreeNode helpBuild(int[] preorder, int preLeft, int preRight, int[] inorder, int inLeft, int inRight) {
if (inRight - inLeft == 0) {
return null;
}
if (inRight - inLeft == 1) {
return new TreeNode(inorder[inLeft]);
}
TreeNode root = new TreeNode(preorder[preLeft]);
int rootIndex = 0;
for (int i = inLeft; i < inRight; i++) {
if (inorder[i] == root.val) {
rootIndex = i;
break;
}
}
root.left = helpBuild(preorder, preLeft + 1, preLeft + 1 + (rootIndex - inLeft), inorder, inLeft, rootIndex);
root.right = helpBuild(preorder, preLeft + 1 + (rootIndex - inLeft), preRight, inorder, rootIndex + 1, inRight);
return root;
}
}
边栏推荐
- 芯片 設計資料下載
- Operation suggestions for today's spot Silver
- Main window in QT learning 27 application
- Explore dry goods! Apifox construction ideas
- 2022 National latest fire-fighting facility operator (primary fire-fighting facility operator) simulation questions and answers
- 2022年全国最新消防设施操作员(初级消防设施操作员)模拟题及答案
- Pytest + allure + Jenkins Environment - - achèvement du remplissage de la fosse
- Linux server development, redis protocol and asynchronous mode
- C language flight booking system
- 即刻报名|飞桨黑客马拉松第三期等你挑战
猜你喜欢
Content of string
Leetcode 90: subset II
[CV] Wu Enda machine learning course notes | Chapter 8
自定义类加载器加载网络Class
[matlab] when matrix multiplication in Simulink user-defined function does not work properly, matrix multiplication module in module library can be used instead
Cnopendata list data of Chinese colleges and Universities
2022年全国最新消防设施操作员(初级消防设施操作员)模拟题及答案
运放电路的反馈电阻上并联一个电容是什么作用
Padavan manually installs PHP
SQL优化的魅力!从 30248s 到 0.001s
随机推荐
[unity] several ideas about circular motion of objects
misc ez_ usb
Qt学习28 主窗口中的工具栏
json 数据展平pd.json_normalize
Redis technology leak detection and filling (II) - expired deletion strategy
Problem solving: unable to connect to redis
【数字IC验证快速入门】17、SystemVerilog学习之基本语法4(随机化Randomization)
央视太暖心了,手把手教你写HR最喜欢的简历
2022 Inner Mongolia latest advanced fire facility operator simulation examination question bank and answers
buuctf misc USB
[quickstart to Digital IC Validation] 15. Basic syntax for SystemVerilog Learning 2 (operator, type conversion, loop, Task / Function... Including practical exercises)
PHP exports millions of data
2022 recurrent training question bank and answers of refrigeration and air conditioning equipment operation
Force buckle 144 Preorder traversal of binary tree
Leetcode 90: subset II
Visualization Document Feb 12 16:42
Leanote private cloud note building
[matlab] when matrix multiplication in Simulink user-defined function does not work properly, matrix multiplication module in module library can be used instead
B. Value sequence thinking
[CV] Wu Enda machine learning course notes | Chapter 8