105. Construct binary tree from preorder and inorder traversal sequence (medium binary tree DFS hash table binary tree)

105. Construction of binary trees from traversal sequences of preorder and middle order

Given two arrays of integers preorder and inorder , among preorder Is the prior traversal of a binary tree , inorder Is the middle order traversal of the same tree , Please construct a binary tree and return its root node .

Example 1:

Input : preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output : [3,9,20,null,null,15,7]
Example 2:

Input : preorder = [-1], inorder = [-1]
Output : [-1]

Tips :

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder and inorder all No repetition Elements
inorder All appear in preorder
preorder Guarantee It is the preorder traversal sequence of binary tree
inorder Guarantee It is the middle order traversal sequence of binary tree

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

analysis

This topic needs to understand the process of preorder traversal and inorder traversal of binary trees , And the relationship between the two .
Method 1 ： Hashtable + recursive
The node order of preorder traversal is ： root -> The pre order traversal of the left subtree -> Preorder traversal of right subtree ;
The node order of middle order traversal is ： The middle order traversal of the left subtree -> root -> Middle order traversal of right subtree ;
By locating the root node in the middle order traversal , You can know the number of nodes of the left subtree and the right subtree , Combining the position of the root node in the preorder traversal, we can get the preorder and inorder traversal results of the left and right subtrees of the root node , The left and right subtrees are constructed recursively and then connected .
To find the root node, you can record the nodes and index positions in the preorder traversal through the hash table , In this way, you can quickly find the corresponding root node in the middle order traversal .
Method 2 ： iteration
According to the characteristics of preorder traversal and inorder traversal , For two consecutive nodes traversed by the preorder u and v, There are two situations ,v yes u The left child node or v Is one of its parent nodes （ Is not necessarily u） Right child of , Combined with the middle order traversal, we can judge when the second situation occurs , The rest of the time v All are u The left child of .
We traverse the array traversed by the previous order , At the same time, use a pointer to traverse the array traversed in the middle order , In the process of traversing the preamble array, store the nodes in the stack , At the same time, judge whether the node is the same as the node in the middle order traversal array pointed by the pointer , Otherwise, the current node is the left child of the previous node , Otherwise, move the pointer to the right and pop up the node at the top of the stack , Until the stack is empty or the node at the top of the stack is the same as the node pointed to by the pointer , At this point, the node pointed to by the pointer is the last pop The right child node of the out node , The bottom element of the stack is the tree that needs to be constructed .

Answer key （Java）

Method 1 ：

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
    
    private Map<Integer, Integer> map = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
    
        int n = preorder.length;
        for (int i = 0; i < n; i++) {
    
            map.put(inorder[i], i);
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }

    private TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
    
        if (preorder_left > preorder_right) {
    
            return null;
        }

		//  The first node in preorder traversal is the root node 
        int preorder_root = preorder_left;
        //  Locate the root node in the middle order traversal 
        int inorder_root = map.get(preorder[preorder_root]);

		//  First set up the root node 
        TreeNode root = new TreeNode(preorder[preorder_root]);
        //  Get the number of nodes in the left subtree 
        int size_left_subtree = inorder_root - inorder_left;
        //  Construct the left subtree and connect the root node 
        root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        //  Construct the right subtree and connect the root node 
        root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }
}

Method 2 ：

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
    
        if (preorder == null || preorder.length == 0) {
    
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        int inorderIndex = 0;
        for (int i = 1; i < preorder.length; i++) {
    
            int preorderVal = preorder[i];
            TreeNode node = stack.peek();
            if (node.val != inorder[inorderIndex]) {
    
                node.left = new TreeNode(preorderVal);
                stack.push(node.left);
            } else {
    
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
    
                    node = stack.pop();
                    inorderIndex++;
                }
                node.right = new TreeNode(preorderVal);
                stack.push(node.right);
            }
        }
        return root;
    }
}