小学生都能看懂的题解 | #输出二叉树的右视图#

解释问题

假设你有一堆小球，每个小球都有不同的编号。现在，这些小球被放在一个神奇的盒子里，形成了一个树形结构。但是，这个盒子有两个洞，你可以从这两个洞看到小球的顺序，一个是前门（前序遍历），另一个是侧门（中序遍历）。你的任务是根据从前门和侧门看到的小球顺序，重建这个盒子内部的样子，并且告诉你站在盒子后面能看到哪些小球。

如何解决问题

第一步：重建盒子（二叉树）

1. 找根节点：
1. 从前门（前序遍历）看到的第一个小球就是盒子的根节点。
2. 分左右：
1. 在侧门（中序遍历）看到的小球里找到根节点，它左边的是左子树，右边的是右子树。
3. 递归构建：
1. 对左子树和右子树重复第一步和第二步，直到没有小球为止。

第二步：找到后面看到的小球（右视图）

1. 从上往下看：
1. 想象你在盒子顶部向下看，每次只记下你看到的第一排中最右边的那个小球。
2. 一层一层来：
1. 一层层地看，每看一层就记下一个最右边的小球。

实现步骤

1. 构建二叉树

• 找到根节点（前序遍历的第一个数字）。
• 在中序遍历中找到这个根节点，确定左右子树的边界。
• 递归地创建左右子树。

2. 获取右视图

• 使用队列进行层次遍历。
• 每次遍历一层时，记录这一层最后一个访问的节点的值。

示例代码

这里用简单的语言来描述代码逻辑：

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public int[] solve(int[] preOrder, int[] inOrder) {
        // 1. 根据前序和中序构建二叉树
        TreeNode root = buildTree(preOrder, inOrder, 0, preOrder.length - 1, 0, inOrder.length - 1);
        
        // 2. 获取右视图
        List<Integer> rightView = rightSideView(root);
        
        // 3. 将结果转换成整型数组返回
        return rightView.stream().mapToInt(i -> i).toArray();
    }

    private TreeNode buildTree(int[] preorder, int[] inorder, int preStart, int preEnd, int inStart, int inEnd) {
        if (preStart > preEnd) return null;

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

        // 在中序遍历中找到根节点的位置
        int index = inStart;
        for (; index <= inEnd; index++) {
            if (inorder[index] == rootVal) break;
        }

        // 左子树的长度
        int leftLength = index - inStart;
        
        // 构建左右子树
        root.left = buildTree(preorder, inorder, preStart + 1, preStart + leftLength, inStart, index - 1);
        root.right = buildTree(preorder, inorder, preStart + leftLength + 1, preEnd, index + 1, inEnd);

        return root;
    }

    private List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

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

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode current = queue.poll();
                if (i == size - 1) {
                    // 只记录每层最后一个节点的值
                    result.add(current.val);
                }
                if (current.left != null) queue.offer(current.left);
                if (current.right != null) queue.offer(current.right);
            }
        }
        return result;
    }
}

如果这篇文章对你有帮助，请点个免费的赞👍，让它帮助更多的人。