This article is participating in the nuggets team number online activity, click to see the dachang spring recruiting positions

I. Title Description:

So what they’re saying is, you’re given a binary tree with a pre-order and a middle-order traversal sequence, and you’re going to build the binary tree from those two sequences. Assume that there are no duplicate numbers in this binary tree.

For example, you are given pre-traversal and middle-traversal sequences: pre-traversal: 1, 2, 4, 8, 16 Middle-traversal sequences: 2, 1, 8, 4, 16 and you return the binary tree constructed from them: 1 / \ 2 4 / \ 8 16Copy the code


Ii. Analysis of Ideas:

Pre-order traversal visits the root node first.

Steps to solve the problem:

  1. Find the root node first: in the preceding ordinal group
  2. Then the left and right sides recursively construct: in the middle ordinal group

Here’s an example:

  1. Now in the pre-ordinal group, take the root node in order
  2. Then according to the root node, in the middle ordinal group

Build the tree for the first time, as shown below:

Build the tree for the second time, as shown in the figure:

You can use a Map to store sequential traversal values and subscripts for quick access.


Three,ACCode:

public class LeetCode_105 {

    // Time: o(n), Space: o(n), Faster: 96.84%
    public TreeNode buildTree(int[] preorder, int[] inorder) {

        Map<Integer, Integer> inPos = new HashMap<>();

        for (int i = 0; i < inorder.length; ++i)
            inPos.put(inorder[i], i);

        return buildTree(preorder, 0, preorder.length - 1.0, inPos);
    }

    private TreeNode buildTree(int[] pre, int preStart, int preEnd, int inStart, Map<Integer, Integer> inPos) {

        if (preStart > preEnd) return null;
        TreeNode root = new TreeNode(pre[preStart]);
        int rootIdx = inPos.get(pre[preStart]);
        int leftLen = rootIdx - inStart;
        root.left = buildTree(pre, preStart + 1, preStart + leftLen, inStart, inPos);
        root.right = buildTree(pre, preStart + leftLen + 1, preEnd, rootIdx + 1, inPos);

        returnroot; }}Copy the code


Iv. Summary:

Tree traversal template

There are four types of tree traversal:

  1. The former sequence traversal
  2. In the sequence traversal
  3. After the sequence traversal
  4. Level traversal

It can also be divided into depth-first traversal (DFS) and breadth-first traversal (BFS)

Hierarchy traversal: Is for breadth-first traversal.

Other traversal: Is for depth-first traversal.

1. Preorder traversal

void traverse(TreeNode root) {
    if (null == root) return;
    
    // Preorder traversal code
    
    traverse(root.left);
    traverse(root.right);
}
Copy the code

2. Middle order traversal

void traverse(TreeNode root) {
    if (null == root) return;
    
    traverse(root.left);
    
    // Preorder traversal code
    
    traverse(root.right);
}
Copy the code

3. Back-order traversal

void traverse(TreeNode root) {
    if (null == root) return;
    
    traverse(root.left);
    traverse(root.right);
    
    // Preorder traversal code
}
Copy the code

4. Hierarchy traversal

Queue simulation

void traverse(TreeNode root) {
    if (null == root) return;
    
    // Initialize the queue to add root to the queue
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    
    while(! q.isEmpty()) { TreeNode cur = q.poll();// Hierarchy traverses code
        System.out.println(root.val);
        
        if(cur.left ! =null) q.offer(cur.left);
        if(cur.right ! =null) q.offer(cur.right); }}Copy the code