Welcome to my personal website. I use this space to share some of my thoughts and software that I write in my free time. Sometimes I also publish photos. If you want to get in touch please use LinkedIn or Mastodon.
Leetcode: Construct Binary Tree from Inorder and Postorder Traversal
Construct a binary tree from in-order and post-order arrays.
The requirement is to understand in-order and post-order traversal. In-Order visits all nodes to the left, then the current node and then all nodes to the right. Post-order visits all nodes to the left of the current node, all nodes to the right of the current node and finally the node itself.
This means, that the root node can immediately identified as the last element in the postorder array. From there we can split the inorder array by getting the index of the element and immediately know that all nodes to the left of the pivot element belong to the left of the item and vice versa. By simply counting the number of elements, we where we need to split the postorder array.
Finally, apply this knowledge in a recursive method (inner) and stop once postorder (or inorder) is empty. Then we know we are below a leaf node.
About the author
Friedrich Ewald is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.