[must] bm41 output the right view of the binary tree [medium +]

Output the right view of the binary tree _ Niuke Tiba _ Cattle from 【 Niuke Tiba 】 Collect high-frequency school recruitment pen interview questions from enterprises , With official explanation , Online Baidu Alibaba Tencent Netease and other Internet famous enterprises written interview simulation test practice , Discuss the classic test questions with Niu Ren , Improve your technical ability in an all-round way https://www.nowcoder.com/practice/c9480213597e45f4807880c763ddd5f0?tpId=295&tqId=1073834&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D295

subject ：

Please traverse according to the preamble of the binary tree , Middle order traversal recovery binary tree , And print out the right view of the binary tree

Data range ： 0≤n≤10000

requirement ： Spatial complexity  O(n), Time complexity  O(n)

Such as the input [1,2,4,5,3],[4,2,5,1,3] when , The result of preorder traversal [1,2,4,5,3] And the result of middle order traversal [4,2,5,1,3] The following binary tree can be reconstructed ：

So the corresponding output is [1,3,5].

Example 1

Input ：

[1,2,4,5,3],[4,2,5,1,3]

Return value ：

[1,3,5]

remarks ：

The value of each node of the binary tree is in the interval [1,10000] Inside , And ensure that the values of each node are different from each other .

Ideas ：

• Two steps ：
  • Recover binary tree according to preorder traversal and inorder traversal ;105. Construction of binary trees from traversal sequences of preorder and middle order
  • Use sequence traversal to get the right view ;199. Right side view of binary tree
  • It is the synthesis of these two topics ;

• Finding the root node in the preorder traversal from the inorder traversal can be optimized using a hash table , Trade space for time , You can traverse the middle order first , Store the relationship between coordinates and values in the middle order traversal in the hash table ;
• In fact, I feel a little divided ;

Code ：

import java.util.*;
public class Solution {
    private Map<Integer, Integer> indexMap;
    // Tree building function 
    // four int The parameters are the subscript of the leftmost node of the preamble , The subscript of the rightmost node of the preamble 
    // The subscript of the leftmost node in the middle order , Coordinates of the rightmost node in the middle order 
    public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left,
                                int preorder_right, int inorder_left, int inorder_right) {
        //  Closing left and closing right will affect this pop-up condition , This leads to a negative number on the right if it is empty ;
        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 = indexMap.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 from the middle order traversal ;
        int size_left_subtree = inorder_root - inorder_left;
        //  The left subtree is constructed recursively , And connect to the root node ;
        //  In the first order traversal 「 from   Left boundary +1  At the beginning  size_left_subtree」 Elements correspond to the middle order traversal 「 from   Left boundary   Start to   Root node localization -1」 The elements of ;
        root.left = myBuildTree(preorder, inorder, preorder_left + 1,
                                preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        //  Construct the right subtree recursively , And connect to the root node 
        //  In the first order traversal 「 from   Left boundary +1+ The number of nodes in the left subtree   Start to   Right border 」 The element corresponding to the middle order traversal 「 from   Root node localization +1  To   Right border 」 The elements of ;
        root.right = myBuildTree(preorder, inorder,
                                 preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1,
                                 inorder_right);
        return root;
    }

    // Level traversal 
    public ArrayList<Integer> rightSideView(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.offer(root);
        while (!q.isEmpty()) {
            // The size in the queue is the node tree of this layer 
            int size = q.size();
            while (size-- != 0) {
                TreeNode temp = q.poll();
                if (temp.left != null)
                    q.offer(temp.left);
                if (temp.right != null)
                    q.offer(temp.right);
                // Rightmost element 
                if (size == 0)
                    res.add(temp.val);
            }
        }
        return res;
    }

    public int[] solve (int[] preorder, int[] inorder) {
        int n = preorder.length;
        //  Construct a hash map , Help us quickly locate the root node 
        indexMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < n; i++) {
            indexMap.put(inorder[i], i);
        }
        // Build up trees 
        TreeNode root = myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
        // Get right view output 
        ArrayList<Integer> temp = rightSideView(root);
        // Convert to array 
        int[] res = new int[temp.size()];
        for (int i = 0; i < temp.size(); i++)
            res[i] = temp.get(i);
        return res;
    }
}