Shulou(Shulou.com)06/01 Report--

Today, I will talk to you about how to construct a binary tree through traversal sequences. maybe many people don't know much about it. in order to make you understand better, the editor has summarized the following content for you. I hope you can get something according to this article.

Algorithm:

The core of this kind of problem is to find the root node by pre-order or post-order traversal, divide it into left and right subtrees by mid-order traversal, and then operate recursively.

Preorder traversal: root node, left subtree, right subtree order traversal: left subtree, right subtree, right subtree post-order traversal: left subtree, right subtree, root node preorder / post-order first find the root node, using the same length of the left / right subtrees of the two traversal scenes, find the left and right subtrees of the middle order.

Topic 1: preorder and intermediate order to construct a binary tree

Https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

Code implementation:

/ * Definition for a binary tree node. * type TreeNode struct {* Val int * Left * TreeNode * Right * TreeNode * * / func buildTree (preorder [] int, inorder [] int) * TreeNode {if len (preorder) = = 0 {return nil} root: = new (TreeNode) root.Val = preorder [0] var i int for i

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.