Example Analysis of ergodic Construction of python binary Tree
Today, I will talk to you about the example analysis of traversing the construction of python binary tree, which may not be well understood by many people. 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.
A binary tree is constructed according to the preorder traversal and intermediate order traversal of a tree.
Note:
You can assume that there are no repeating elements in the tree.
For example, give the
Preorder traversal preorder = [3pm 9pm 20je 15rem 7]
Traversing in the middle order inorder = [9 ~ 1 ~ 3 ~ 15 ~ 20 ~ 7]
Return the following binary tree:
three
/\
9 20
/\
15 7
Ideas for solving the problem:
1, if the preorder is traversed, the first must be the root
2, if traversing in the middle order, the left side of the element that is equal to the root element must be on the left subtree, and the position of the root element is I
3. Preorder traversal. The element whose length is iSig1 must be in the left subtree.
4, recursive solution
/ * 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) < 1 | len (inorder) < 1 {return nil} if len (preorder) = = 1 {return & TreeNode {Val: preorder [0],}} if len (inorder) = = 1 {return & TreeNode {Val: inorder [0],}}
I: = 0 for; I < len (inorder); iTunes + {if preorder [0] = = inorder [I] {break}} if I = = len (inorder) {return nil} h: = & TreeNode {Val: preorder [0],}
If I = 0 {h.Right = buildTree (preorder [1:], inorder [iTun1:])} else if i = = len (inorder)-1 {h.Left = buildTree (preorder [1:], inorder [: I])} else {h.Left = buildTree (preorder [1:i+1], inorder [: I]) h.Right = buildTree (preorder [iTun1:], inorder [iTun1:])} return h}
A binary tree is constructed according to the middle order traversal and post order traversal of a tree.
Note:
You can assume that there are no repeating elements in the tree.
For example, give the
Traversing in the middle order inorder = [9 ~ 1 ~ 3 ~ 15 ~ 20 ~ 7]
Traversing through postorder = [9, 15, 7, 20, 3]
Return the following binary tree:
three
/\
9 20
/\
15 7
Ideas for solving the problem:
1, if you traverse in post-order, the last one must be the root.
2, if traversing in the middle order, the left side of the element that is equal to the root element must be on the left subtree, and the position of the root element is I
3, traversing in post-order, the element with the preceding length of iSig1 must be in the left subtree.
4, recursive solution
/ * Definition for a binary tree node. * type TreeNode struct {* Val int * Left * TreeNode * Right * TreeNode * * / func buildTree (inorder [] int, postorder [] int) * TreeNode {if len (inorder)
