题解 | 输出二叉树的右视图

1、解题思路

1. 重建二叉树：前序遍历的第一个元素是根节点。在中序遍历中找到根节点的位置，左侧是左子树，右侧是右子树。递归构建左子树和右子树。
2. 获取右视图：使用层序遍历（BFS），记录每一层的最后一个节点即为右视图节点。

2、代码实现

C++

#include <ios>
#include <unordered_map>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求二叉树的右视图
     * @param preOrder int整型vector 先序遍历
     * @param inOrder int整型vector 中序遍历
     * @return int整型vector
     */
    vector<int> solve(vector<int>& preOrder, vector<int>& inOrder) {
        // write code here
        unordered_map<int, int> inMap;
        for (int i = 0; i < inOrder.size(); ++i) {
            inMap[inOrder[i]] = i;
        }
        TreeNode* root = buildTree(preOrder, 0, preOrder.size() - 1, inOrder, 0, inOrder.size() - 1, inMap);
        return rightView(root);
    }

    TreeNode* buildTree(vector<int>& preOrder, int preStart, int preEnd, vector<int>& inOrder, int inStart, int inEnd, unordered_map<int, int>& inMap) {
        if (preStart > preEnd || inStart > inEnd) {
            return nullptr;
        }

        int rootVal = preOrder[preStart];
        TreeNode* root = new TreeNode(rootVal);

        int rootIndex = inMap[rootVal];
        int leftSubtreeSize = rootIndex - inStart;

        root->left = buildTree(preOrder, preStart + 1, preStart + leftSubtreeSize, inOrder, inStart, rootIndex - 1, inMap);
        root->right = buildTree(preOrder, preStart + leftSubtreeSize + 1, preEnd, inOrder, rootIndex + 1, inEnd, inMap);

        return root;
    }

    vector<int> rightView(TreeNode* root) {
        vector<int> result;
        if (!root) {
            return result;
        }

        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            int levelSize = q.size();
            for (int i = 0; i < levelSize; ++i) {
                TreeNode* node = q.front();
                q.pop();

                if (i == levelSize - 1) {
                    result.push_back(node->val);
                }

                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
            }
        }

        return result;
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求二叉树的右视图
     * @param preOrder int整型一维数组 先序遍历
     * @param inOrder int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public int[] solve (int[] preOrder, int[] inOrder) {
        // write code here
        Map<Integer, Integer> inMap = new HashMap<>();
        for (int i = 0; i < inOrder.length; i++) {
            inMap.put(inOrder[i], i);
        }
        TreeNode root = buildTree(preOrder, 0, preOrder.length - 1, inOrder, 0, inOrder.length - 1, inMap);
        return rightView(root);
    }

    private TreeNode buildTree(int[] preOrder, int preStart, int preEnd, int[] inOrder, int inStart, int inEnd,  Map<Integer, Integer> inMap) {
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }

        int rootVal = preOrder[preStart];
        TreeNode root = new TreeNode(rootVal);

        int rootIndex = inMap.get(rootVal);
        int leftSubtreeSize = rootIndex - inStart;

        root.left = buildTree(preOrder, preStart + 1, preStart + leftSubtreeSize, inOrder, inStart, rootIndex - 1, inMap);
        root.right = buildTree(preOrder, preStart + leftSubtreeSize + 1, preEnd, inOrder, rootIndex + 1, inEnd, inMap);

        return root;
    }

    private int[] rightView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return new int[0];
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();

                if (i == levelSize - 1) {
                    result.add(node.val);
                }

                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }

        return result.stream().mapToInt(Integer::intValue).toArray();
    }
}

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 求二叉树的右视图
# @param preOrder int整型一维数组 先序遍历
# @param inOrder int整型一维数组 中序遍历
# @return int整型一维数组
#
from collections import deque


class Solution:
    def solve(self, preOrder: List[int], inOrder: List[int]) -> List[int]:
        # write code here
        in_map = {val: idx for idx, val in enumerate(inOrder)}
        root = self.buildTree(
            preOrder, 0, len(preOrder) - 1, inOrder, 0, len(inOrder) - 1, in_map
        )
        return self.rightView(root)

    def buildTree(self, preOrder, preStart, preEnd, inOrder, inStart, inEnd, in_map):
        if preStart > preEnd or inStart > inEnd:
            return None

        root_val = preOrder[preStart]
        root = TreeNode(root_val)

        root_index = in_map[root_val]
        left_subtree_size = root_index - inStart

        root.left = self.buildTree(
            preOrder,
            preStart + 1,
            preStart + left_subtree_size,
            inOrder,
            inStart,
            root_index - 1,
            in_map,
        )
        root.right = self.buildTree(
            preOrder,
            preStart + left_subtree_size + 1,
            preEnd,
            inOrder,
            root_index + 1,
            inEnd,
            in_map,
        )

        return root

    def rightView(self, root):
        result = []
        if not root:
            return result

        queue = deque([root])

        while queue:
            level_size = len(queue)
            for i in range(level_size):
                node = queue.popleft()

                if i == level_size - 1:
                    result.append(node.val)

                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

        return result

3、复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)。