LeetCode 补充题 198. 由前序和中序遍历求二叉树右视图

2026-09-14 HGNULB 约 5 分钟

文章信息 2 个分类 4 个标签

分类

补充题中等

题目描述

[!green]

牛客原题： ✅ 补充题 198. 由前序和中序遍历求二叉树右视图

给定同一棵二叉树的前序遍历 preorder 与中序遍历 inorder，返回从上到下的右视图节点值。

示例 1：

输入： preorder = [1,2,3], inorder = [2,1,3]
输出： [1,3]

提示：

两数组长度相等且描述合法的同一棵树。
节点值互不相同。
允许空树。

题意分析

前序和中序在节点值互不相同的条件下能唯一确定树。先用两种遍历恢复左右子树的边界，再按层取最右节点，可以把下标划分与视图提取分开处理。

解法：重建二叉树 + 层序遍历

核心思路

[!blue]

把题目拆成两个能独立讲清楚的步骤：先重建树，再取右视图。

重建时，前序区间的第一项是根；用中序下标表找到根的位置，就能算出左子树有多少节点。前序根的下一项开始是左子树，跨过整段左子树后才是右子树；递归只处理各自对应的中序区间，空区间返回空节点。

树建好后按层 BFS。每层开始时固定队列长度，孩子按左、右顺序入队；本层最后一个出队节点就是从右侧能看见的节点。两步都只按节点做线性处理。

解题步骤

建立节点值到中序下标的映射，避免递归时反复扫描。

以前序首项为根，用中序根位置计算左子树长度，递归构建左右子树。

将重建的根入队，每层开始固定当前队列长度。

孩子先左后右入队，保存本层最后一个出队节点的值。

代码实现

class Solution {
    public List<Integer> rightView(int[] preorder, int[] inorder) {
        return rightSideView(buildTree(preorder, inorder));
    }

    private Map<Integer, Integer> indexMap;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        indexMap = new HashMap<>();

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

        return build(preorder, 0, 0, inorder.length - 1);
    }

    private TreeNode build(int[] preorder, int preRoot, int inLeft, int inRight) {
        if (inLeft > inRight) {
            return null;
        }

        int rootVal = preorder[preRoot];
        TreeNode root = new TreeNode(rootVal);
        int rootIdx = indexMap.get(rootVal);
        int leftSize = rootIdx - inLeft;

        root.left = build(preorder, preRoot + 1, inLeft, rootIdx - 1);
        root.right = build(preorder, preRoot + leftSize + 1, rootIdx + 1, inRight);

        return root;
    }

    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();

        if (root == null) {
            return res;
        }

        Queue<TreeNode> queue = new ArrayDeque<>();

        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) {
                    res.add(node.val);
                }

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

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

        return res;
    }
}

func buildTree(preorder []int, inorder []int) *TreeNode {
    indexMap := make(map[int]int)
    for i, num := range inorder {
        indexMap[num] = i
    }

    var build func(preRoot, inLeft, inRight int) *TreeNode
    build = func(preRoot, inLeft, inRight int) *TreeNode {
        if inLeft > inRight {
            return nil
        }

        rootVal := preorder[preRoot]
        root := &TreeNode{Val: rootVal}
        rootIdx := indexMap[rootVal]
        leftSize := rootIdx - inLeft

        root.Left = build(preRoot+1, inLeft, rootIdx-1)
        root.Right = build(preRoot+leftSize+1, rootIdx+1, inRight)
        return root
    }

    return build(0, 0, len(inorder)-1)
}

func rightSideView(root *TreeNode) []int {
    res := make([]int, 0)
    if root == nil {
        return res
    }

    queue := []*TreeNode{
        root,
    }
    for len(queue) > 0 {
        levelSize := len(queue)
        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            if i == levelSize-1 {
                res = append(res, node.Val)
            }

            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
    }

    return res
}

func rightView(preorder []int, inorder []int) []int {
    return rightSideView(buildTree(preorder, inorder))
}

复杂度分析

时间复杂度：$O(n)$。

空间复杂度：$O(n)$，包括重建的树、索引表和遍历队列。

关键点总结

[!green]

用前序根节点和中序下标表划分子树并重建，再逐层收集最右节点。

易错点总结

[!yellow]

递归先判断区间为空，再读取前序根值，兼容空树。

右子树在前序中的起点，需要越过当前根和整个左子树。

每层固定节点数后取最后一项，不能误收集下一层已入队的孩子。

相似题目

题目	难度	关联与区别
199. 二叉树的右视图	中等	右视图的逐层取最右节点过程相同；该题直接接收树根，本题先根据前序、中序序列重建二叉树。
105. 从前序与中序遍历序列构造二叉树	中等	本题先用前序根节点与中序下标划分左右子树，完整复用该题的重建算法，再对结果树计算右视图。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/573520227466

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！