Front and middle order traversal sequence construction binary tree, recursion + hash table, JavaScript, detailed comments

LeeChen 2021-01-21 04:51:48
middle order traversal sequence construction


Original link :leetcode-cn.com/problems/co…

Their thinking :

  1. Refer to the Many solutions , Gradually optimize ( Supplement the solution of foreign tycoons ) and The demo 105. Construction of binary trees from traversal sequences of preorder and middle order .
  2. Suppose there is a binary tree as follows :
 1
/ \
2 3
/ \ / \
4 5 6 7
 Copy code 

The result of preorder traversal is : [1,2,4,5,3,6,7] The result of middle order traversal is : [4,2,5,1,6,3,7]

  1. You can take it from the root node 1, Split into two subtrees , as follows :

The left subtree :

 2
/ \
4 5
 Copy code 

The result of preorder traversal is : [2,4,5] The result of middle order traversal is : [4,2,5]

Right subtree :

 3
/ \
6 7
 Copy code 

The result of preorder traversal is : [3,6,7] The result of middle order traversal is : [6,3,7]

  1. We can follow the steps 3 Laws , Calculate the index in the original array corresponding to the front middle order traversal of the left and right subtrees , You can know their corresponding values :

    • The preorder traversal index of the left subtree :
    preLeft = preLeft + 1, // The preorder of the left subtree traverses the left boundary
    preRight = preLeft + nodeCount, // The current left border plus the number of subtree nodes , That is, the preorder of the left subtree traverses the right boundary
     Copy code 
    • Middle order traversal index of left subtree :
    inLeft = inLeft, // The middle order of the left subtree traverses the left boundary
    inRight = rootIndex - 1, // The middle order of the left subtree traverses the right boundary
     Copy code 
    • The preorder traversal index of the right subtree :
    preLeft = preLeft + nodeCount + 1, // The current left boundary plus the number of subtree nodes plus 1, That is, the preorder of the right subtree traverses the left boundary
    preRight = preRight, // The preorder of the right subtree traverses the right boundary
     Copy code 
    • The middle order traversal index of the right subtree :
    inLeft = rootIndex + 1, // The middle order of the right subtree traverses the left boundary
    inRight = inRight, // The middle order of the right subtree traverses the right boundary
     Copy code 
  2. Through the steps 4 Analysis of , We can recurse according to the following logic :

    • For each recursion preorder[preLeft] The value of generates a root node .
    • Through preorder[preLeft] Find it in inorder Position in rootIndex, Calculate the index of the front middle order traversal of the subtree in the original array , Recursion of the next layer is carried out respectively .
    • Every time I recurs ,inorder The position of each value in is fixed , So just use... Before recursion Map Cache the relationship between all values and indexes , After use O(1) The query can be completed with the time complexity of .
    • The left and right subtrees generated by the lower layer recursion , Connect to the current root node .
    • When the recursion completes, the current root node is returned , Recursive connection for the next layer .
    • preorder and inorder After all the values in are generated by nodes , That is to say, the generation of the whole binary tree is completed .
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {number[]} preorder
* @param {number[]} inorder
* @return {TreeNode}
*/
var buildTree = function (preorder, inorder) {
/**
* @description  Use the pre middle order to traverse the fragment of the result , Recursively generate a binary tree
* @param {number} preLeft // The left boundary of each subtree in the preorder traversal
* @param {number} preRight // The right boundary of each subtree in the preorder traversal
* @param {number} inLeft // The left boundary of each subtree in the middle order traversal
* @param {number} inRight // The right boundary of each subtree in the middle order traversal
* @return {TreeNode}
*/
function buildBinaryTree(preLeft, preRight, inLeft, inRight) {
// When the left bound of the truncated array fragment is larger than the right bound , Indicates that the current array used to construct the subtree is empty , Exit loop 
if (preLeft > preRight) {
// When the array is empty , It means that there is no node to generate at present , return null
// Let the node of the upper layer left and right Pointer to null
return null;
}
// Cache the value of the root node 
const rootVal = preorder[preLeft];
// Create a node with the current value , It is the root node of a tree 
const root = new TreeNode(rootVal);
// Find the position of the current root node in the array 
const rootIndex = inorder.indexOf(rootVal);
// The difference between the left bound of the middle order traversal and the root node is the number of nodes in the subtree 
// Because the left boundary will always exist , So counting to the left always gets the number of nodes in the subtree 
const nodeCount = rootIndex - inLeft;
// Calculate the index of the left subtree of the array , Down the recursive 
// Connect the current root node with the generated left subtree 
root.left = buildBinaryTree(
preLeft + 1, // The preorder of the left subtree traverses the left boundary 
preLeft + nodeCount, // The current left border plus the number of subtree nodes , That is, the preorder of the left subtree traverses the right boundary 
inLeft, // The middle order of the left subtree traverses the left boundary 
rootIndex - 1, // The middle order of the left subtree traverses the right boundary 
);
// Calculate the index of the right subtree of the array , Down the recursive 
// Connect the current root node with the generated right subtree 
root.right = buildBinaryTree(
preLeft + nodeCount + 1, // The current left boundary plus the number of subtree nodes plus 1, That is, the preorder of the right subtree traverses the left boundary 
preRight, // The preorder of the right subtree traverses the right boundary 
rootIndex + 1, // The middle order of the right subtree traverses the left boundary 
inRight, // The middle order of the right subtree traverses the right boundary 
);
// Return the root node for the upper node to connect 
return root;
}
// Generate a binary tree and return 
return buildBinaryTree(0, preorder.length - 1, 0, preorder.length - 1);
};
 Copy code 
版权声明
本文为[LeeChen]所创,转载请带上原文链接,感谢
https://javamana.com/2021/01/20210121044620188y.html

  1. 【计算机网络 12(1),尚学堂马士兵Java视频教程
  2. 【程序猿历程,史上最全的Java面试题集锦在这里
  3. 【程序猿历程(1),Javaweb视频教程百度云
  4. Notes on MySQL 45 lectures (1-7)
  5. [computer network 12 (1), Shang Xuetang Ma soldier java video tutorial
  6. The most complete collection of Java interview questions in history is here
  7. [process of program ape (1), JavaWeb video tutorial, baidu cloud
  8. Notes on MySQL 45 lectures (1-7)
  9. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  10. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  11. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  12. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  13. 【递归,Java传智播客笔记
  14. [recursion, Java intelligence podcast notes
  15. [adhere to painting for 386 days] the beginning of spring of 24 solar terms
  16. K8S系列第八篇(Service、EndPoints以及高可用kubeadm部署)
  17. K8s Series Part 8 (service, endpoints and high availability kubeadm deployment)
  18. 【重识 HTML (3),350道Java面试真题分享
  19. 【重识 HTML (2),Java并发编程必会的多线程你竟然还不会
  20. 【重识 HTML (1),二本Java小菜鸟4面字节跳动被秒成渣渣
  21. [re recognize HTML (3) and share 350 real Java interview questions
  22. [re recognize HTML (2). Multithreading is a must for Java Concurrent Programming. How dare you not
  23. [re recognize HTML (1), two Java rookies' 4-sided bytes beat and become slag in seconds
  24. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  25. RPC 1: how to develop RPC framework from scratch
  26. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  27. RPC 1: how to develop RPC framework from scratch
  28. 一次性捋清楚吧,对乱糟糟的,Spring事务扩展机制
  29. 一文彻底弄懂如何选择抽象类还是接口,连续四年百度Java岗必问面试题
  30. Redis常用命令
  31. 一双拖鞋引发的血案,狂神说Java系列笔记
  32. 一、mysql基础安装
  33. 一位程序员的独白:尽管我一生坎坷,Java框架面试基础
  34. Clear it all at once. For the messy, spring transaction extension mechanism
  35. A thorough understanding of how to choose abstract classes or interfaces, baidu Java post must ask interview questions for four consecutive years
  36. Redis common commands
  37. A pair of slippers triggered the murder, crazy God said java series notes
  38. 1、 MySQL basic installation
  39. Monologue of a programmer: despite my ups and downs in my life, Java framework is the foundation of interview
  40. 【大厂面试】三面三问Spring循环依赖,请一定要把这篇看完(建议收藏)
  41. 一线互联网企业中,springboot入门项目
  42. 一篇文带你入门SSM框架Spring开发,帮你快速拿Offer
  43. 【面试资料】Java全集、微服务、大数据、数据结构与算法、机器学习知识最全总结,283页pdf
  44. 【leetcode刷题】24.数组中重复的数字——Java版
  45. 【leetcode刷题】23.对称二叉树——Java版
  46. 【leetcode刷题】22.二叉树的中序遍历——Java版
  47. 【leetcode刷题】21.三数之和——Java版
  48. 【leetcode刷题】20.最长回文子串——Java版
  49. 【leetcode刷题】19.回文链表——Java版
  50. 【leetcode刷题】18.反转链表——Java版
  51. 【leetcode刷题】17.相交链表——Java&python版
  52. 【leetcode刷题】16.环形链表——Java版
  53. 【leetcode刷题】15.汉明距离——Java版
  54. 【leetcode刷题】14.找到所有数组中消失的数字——Java版
  55. 【leetcode刷题】13.比特位计数——Java版
  56. oracle控制用户权限命令
  57. 三年Java开发,继阿里,鲁班二期Java架构师
  58. Oracle必须要启动的服务
  59. 万字长文!深入剖析HashMap,Java基础笔试题大全带答案
  60. 一问Kafka就心慌?我却凭着这份,图灵学院vip课程百度云