[B] [C] [D]

The 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 duplicated elements in the tree.

For example, given

Order = [9,3,15,20,7] postorder = [9,15,7,20,3]Copy the code

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7
Copy the code

Their thinking

This topic mainly investigates our understanding and application of tree middle order traversal and subsequent traversal.

Because the order of the post-traversal is the left and right roots, the last element of the post-traversal sequence must be the value of the root node. And because the order of middle-order traversal is left root right, we can split the left and right subtrees according to the value of the root node. In addition, the middle-order traversal and post-order traversal only differ in the order of node values, but have the same number of elements. Therefore, the middle-order traversal sequence can intercept the post-order traversal sequence of the left subtree according to the length of the middle-order traversal left subtree, and the rest is the post-order traversal sequence of the right subtree. So when there are no elements in the interval, it’s a null node, which is the exit condition of the recursive function. Then, in the backtracking process of the recursive function, we can construct a binary tree according to the current root node value and the return values of the left and right subtrees. When the backtracking is completed, a complete binary tree is obtained.

The demo

Code implementation

Var buildTree = function(inorder, postorder) {function createTree(l1, R1,l2,r2){ Return null if(l1>r1) return null; // Get root value const root = postorder[r2]; Let tail = l1-1; let tail = l1-1; while(tail<r1&&inorder[tail+1]! ==root) tail++ // const diff = tail-l1; Return new TreeNode(root, createTree(l1,tail,l2,l2+diff), createTree(L1,tail,l2 +diff), createTree(l1,tail,l2 +diff), CreateTree (tail+2,r1,l2+diff+1, R2-1))} const len = inorder.length; Return createTree(0,len-1,0,len-1)};Copy the code

At this point we are done with Leetcode-106 – constructing a binary tree by traversing the sequence in middle and rear order

If you have any questions or suggestions, please leave a comment!