This is the 30th day of my participation in the Wenwen Challenge

Constructing a binary tree by traversing pre-order and middle-order sequences (105)

Topic describes

The binary tree is constructed according to the pre-order traversal and middle-order traversal of a tree.

Note: You can assume that there are no duplicated elements in the tree.

For example, given

Preorder = [3,9,20,15,7] inorder = [9,3,15,20,7]Copy the code

Return the following binary tree:

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

Thought analysis

In order to find our original binary tree, we need to know the characteristics of the pre-traversal, the root node is in the first position of the array, and the middle traversal, the root node is in the middle (if there is data to the left). We can distinguish the indexes of the left and right binary trees for preorder and Inorder respectively.

The root node is then pulled out, and the left node is indexed according to the preorder and inorder positions, as well as the right.

The code shown

Solution a:

public TreeNode buildTree(int[] preorder, int[] inorder) {
        return myBuildTree(preorder,0,preorder.length - 1,inorder,0,inorder.length - 1);
    }

    private TreeNode myBuildTree(int[] preorder,int i,int j,int[] inorder,int p,int r){
        if(i > j){
            return null;
        }
        TreeNode root = new TreeNode(preorder[i]);
        int q = p;
        while(q <= r && preorder[i] ! = inorder[q]){ q++; }int leftTreeSize = q-p;
        TreeNode left = myBuildTree(preorder,i+1,i+leftTreeSize,inorder,p,q-1);
        TreeNode right = myBuildTree(preorder,i+leftTreeSize+1,j,inorder,q+1,r);
        root.left = left;
        root.right = right;
        return root;
    }
Copy the code

Constructing binary tree according to preorder and subsequent traversal

Topic describes

Returns any binary tree that matches the given pre – and post-traversal.

The values in pre and Post traversals are different positive integers.

Example 1:

Input: the pre =,2,4,5,3,6,7 [1], the post =,5,2,6,7,3,1 [4] output:,2,3,4,5,6,7 [1]Copy the code

Tip:

  • 1 <= pre.length == post.length <= 30
  • Pre [] and post[] are 1, 2… , pre-length
  • Each input is guaranteed to have at least one answer. If there are multiple answers, one of them can be returned.

Thought analysis

The problem and is very similar to the above subject, the front is the preorder traversal and sequence traversal, here are our preorder traversal and subsequent traversal, according to the preorder traversal sequence and sequence traversal sequence to find us after the original binary tree, first we need to know the characteristics of the preorder traversal, the root node is the first position in the array, then the sequence traversal, the root node is at the bottom. We can distinguish the indexes of the left and right binary trees for the Pre and POST arrays respectively.

Then pull out the root node, the left node according to the index corresponding to the pre and post positions, and the right node.

The code shown

Solution a:

public TreeNode constructFromPrePost(int[] pre, int[] post) {
        return myBuildTree(pre,0,pre.length - 1,post,0,post.length - 1);
    }

    private TreeNode myBuildTree(int[] pre,int i,int j,int[] post,int p,int r){
        if(i > j){
            return null;
        }
        TreeNode root = new TreeNode(pre[i]);
        if(i == j){
            return root;
        }
        int q = p;
        while(q < r-1&& post[q] ! = pre[i+1]){
            q++;
        }
        int leftTreeSize = q-p+1;

        TreeNode left = myBuildTree(pre,i+1,i+leftTreeSize,post,p,q);
        TreeNode right = myBuildTree(pre,i+leftTreeSize+1,j,post,q+1,r-1);
        root.left = left;
        root.right = right;
        return root;

    }
Copy the code

conclusion

The first, middle and last order traversal of binary tree is the basic skill that we must master.