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

题目的主要信息：

• 利用二叉树中序遍历结果及前序遍历结果构建一棵二叉树
• 打印二叉树的右视图，即二叉树每层最右边的节点元素
• 节点值互不相同

举一反三：

学习完本题的思路你可以解决如下题目：

BM40. 重建二叉树

BM38. 在二叉树中找到两个节点的最近公共祖先

BM29. 二叉树中和为某一值的路径（一）

BM26. 求二叉树的层次遍历

方法一：递归建树+深度优先搜索（推荐使用）

知识点1：二叉树递归

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。

而二叉树的递归，则是将某个节点的左子树、右子树看成一颗完整的树，那么对于子树的访问或者操作就是对于原树的访问或者操作的子问题，因此可以自我调用函数不断进入子树。

知识点2：深度优先搜索（dfs） 深度优先搜索一般用于树或者图的遍历，其他有分支的（如二维矩阵）也适用。它的原理是从初始点开始，一直沿着同一个分支遍历，直到该分支结束，然后回溯到上一级继续沿着一个分支走到底，如此往复，直到所有的节点都有被访问到。

知识点3：哈希表

哈希表是一种根据关键码（key）直接访问值（value）的一种数据结构。而这种直接访问意味着只要知道key就能在$O(1)O(1)$时间内得到value，因此哈希表常用来统计频率、快速检验某个元素是否出现过等。

思路：

可以发现解这道题，我们有两个步骤：

1. 建树
2. 打印右视图

首先建树方面，前序遍历是根左右的顺序，中序遍历是左根右的顺序，因为节点值互不相同，我们可以根据在前序遍历中找到根节点（每个子树部分第一个就是），再在中序遍历中找到对应的值，从其左右分割开，左边就是该树的左子树，右边就是该树的右子树，于是将问题划分为了子问题。

而打印右视图即找到二叉树每层最右边的节点元素，我们可以采取dfs（深度优先搜索）遍历树，根据记录的深度找到最右值。

具体做法：

• step 1：首先检查两个遍历序列的大小，若是为0，则空树不用打印。
• step 2：建树函数根据上述说，每次利用前序遍历第一个元素就是根节点，在中序遍历中找到它将二叉树划分为左右子树，利用l1 r1 l2 r2分别记录子树部分在数组中分别对应的下标，并将子树的数组部分送入函数进行递归。
• step 3：dfs打印右视图时，使用哈希表存储每个深度对应的最右边节点，初始化两个栈辅助遍历，第一个栈记录dfs时的节点，第二个栈记录遍历到的深度，根节点先入栈。
• step 4：对于每个访问的节点，每次左子节点先进栈，右子节点再进栈，这样访问完一层后，因为栈的先进后出原理，每次都是右边被优先访问，因此我们在哈希表该层没有元素时，添加第一个该层遇到的元素就是最右边的节点。
• step 5：使用一个变量逐层维护深度最大值，最后遍历每个深度，从哈希表中读出每个深度的最右边节点加入数组中。

图示：

Java实现代码：

import java.util.*;
public class Solution {
    //建树函数
    //四个int参数分别是前序最左节点下标，前序最右节点下标
    //中序最左节点下标，中序最右节点坐标
    public TreeNode buildTree(int[] xianxu, int l1, int r1, int[] zhongxu, int l2, int r2){
        if(l1 > r1 || l2 > r2)
            return null;
        //构建节点
        TreeNode root = new TreeNode(xianxu[l1]);    
        //用来保存根节点在中序遍历列表的下标
        int rootIndex = 0;    
        //寻找根节点
        for(int i = l2; i <= r2; i++){
            if(zhongxu[i] == xianxu[l1]){
                rootIndex = i;
                break;
            }
        }
        //左子树大小
        int leftsize = rootIndex - l2;    
        //右子树大小
        int rightsize = r2 - rootIndex;    
        //递归构建左子树和右子树
        root.left = buildTree(xianxu, l1 + 1, l1 + leftsize, zhongxu, l2 , l2 + leftsize - 1);
        root.right = buildTree(xianxu, r1 - rightsize + 1, r1, zhongxu, rootIndex + 1, r2);
        return root;
    }
    
    //深度优先搜索函数
    public ArrayList<Integer> rightSideView(TreeNode root) {
        //右边最深处的值
        Map<Integer, Integer> mp = new HashMap<Integer, Integer>();
        //记录最大深度
        int max_depth = -1; 
        //维护深度访问节点
        Stack<TreeNode> nodes = new Stack<TreeNode>(); 
        //维护dfs时的深度
        Stack<Integer> depths = new Stack<Integer>();  
        nodes.push(root); 
        depths.push(0);
        while(!nodes.isEmpty()){
            TreeNode node = nodes.pop();
            int depth = depths.pop();
            if(node != null){
            	//维护二叉树的最大深度
                max_depth = Math.max(max_depth, depth);
                //如果不存在对应深度的节点我们才插入
                if(mp.get(depth) == null)
                    mp.put(depth, node.val);
                nodes.push(node.left);
                nodes.push(node.right);
                depths.push(depth + 1);
                depths.push(depth + 1);
            }
        }
        ArrayList<Integer> res = new ArrayList<Integer>();
        //结果加入链表
        for(int i = 0; i <= max_depth; i++) 
            res.add(mp.get(i));
        return res;
    }
    
    public int[] solve (int[] xianxu, int[] zhongxu) {
        //空节点
        if(xianxu.length == 0) 
            return new int[0];
        //建树
        TreeNode root = buildTree(xianxu, 0, xianxu.length - 1, zhongxu, 0, zhongxu.length - 1);
        //获取右视图输出
        ArrayList<Integer> temp = rightSideView(root); 
        //转化为数组
        int[] res = new int[temp.size()]; 
        for(int i = 0; i < temp.size(); i++)
            res[i] = temp.get(i);
        return res;
    }
}

C++实现代码：

class Solution {
public:
    //建树函数
    //四个int参数分别是前序最左节点下标，前序最右节点下标
    //中序最左节点下标，中序最右节点坐标
    TreeNode* buildTree(vector<int>& xianxu, int l1, int r1, vector<int>& zhongxu, int l2, int r2) {
        if(l1 > r1 || l2 > r2)
            return NULL;
        //构建节点
        TreeNode* root = new TreeNode(xianxu[l1]); 
        //用来保存根节点在中序遍历列表的下标  
        int rootIndex = 0;    
        //寻找根节点
        for(int i = l2; i <= r2; i++){
            if(zhongxu[i] == xianxu[l1]){
                rootIndex = i;
                break;
            }
        }
        //左子树大小
        int leftsize = rootIndex - l2;    
        //右子树大小
        int rightsize = r2 - rootIndex;    
        //递归构建左子树和右子树
        root->left = buildTree(xianxu, l1 + 1, l1 + leftsize, zhongxu, l2 , l2 + leftsize - 1);
        root->right = buildTree(xianxu, r1 - rightsize + 1, r1, zhongxu, rootIndex + 1, r2);
        return root;
    }
    //深度优先搜索函数
    vector<int> rightSideView(TreeNode* root) {
        //右边最深处的值
        unordered_map<int, int> mp;
        //记录最大深度
        int max_depth = -1; 
        //维护深度访问节点
        stack<TreeNode*> nodes; 
        //维护dfs时的深度
        stack<int> depths;  
        nodes.push(root); 
        depths.push(0);
        while (!nodes.empty()){
            TreeNode* node = nodes.top();
            nodes.pop();
            int depth = depths.top();
            depths.pop();
            if (node != NULL) {
            	//维护二叉树的最大深度
                max_depth = max(max_depth, depth);
                //如果不存在对应深度的节点我们才插入
                if (mp.find(depth) == mp.end())
                    mp[depth] =  node->val;
                nodes.push(node->left);
                nodes.push(node->right);
                depths.push(depth + 1);
                depths.push(depth + 1);
            }
        }
        vector<int> res;
        for (int i = 0; i <= max_depth; i++)
            res.push_back(mp[i]);
        return res;
    }
    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
        vector<int> res;
        //空节点
        if(xianxu.size() == 0) 
            return res;
        //建树
        TreeNode* root = buildTree(xianxu, 0, xianxu.size() - 1, zhongxu, 0, zhongxu.size() - 1);
        //找每一层最右边的节点
        return rightSideView(root);
    }
};

Python实现代码

from collections import defaultdict

class Solution:
    # 建树函数
    # 四个int参数分别是前序最左节点下标，前序最右节点下标
    # 中序最左节点下标，中序最右节点坐标
    def buildTree(self, xianxu: List[int], l1: int, r1: int, zhongxu: List[int], l2: int, r2: int) -> TreeNode:
        if l1 > r1 or l2 > r2:
            return None
        # 构建节点
        root = TreeNode(xianxu[l1])    
        # 用来保存根节点在中序遍历列表的下标
        rootIndex = 0    
        # 寻找根节点
        for i in range(l2, r2+1):
            if zhongxu[i] == xianxu[l1]:
                rootIndex = i
                break
        # 左子树大小
        leftsize = rootIndex - l2    
        # 右子树大小
        rightsize = r2 - rootIndex    
        # 递归构建左子树和右子树
        root.left = self.buildTree(xianxu, l1 + 1, l1 + leftsize, zhongxu, l2 , l2 + leftsize - 1)
        root.right = self.buildTree(xianxu, r1 - rightsize + 1, r1, zhongxu, rootIndex + 1, r2)
        return root
    def rightSideView(self, root: TreeNode):
        # 右边最深处的值
        mp = defaultdict(int) 
        # 记录最大深度
        max_depth = -1 
        # 维护深度访问节点和维护dfs时的深度
        nodes, depths= [], [] 
        nodes.append(root)
        depths.append(0)
        while nodes:
            node = nodes[-1]
            nodes.pop()
            depth = depths[-1]
            depths.pop()
            if node:
            	# 维护二叉树的最大深度
                max_depth = max([max_depth, depth])
                # 如果不存在对应深度的节点我们才插入
                if mp[depth] == 0:
                    mp[depth] =  node.val
                nodes.append(node.left)
                nodes.append(node.right)
                depths.append(depth + 1)
                depths.append(depth + 1)
        res = []
        for i in range(max_depth + 1):
            res.append(mp[i])
        return res
    def solve(self , xianxu: List[int], zhongxu: List[int]) -> List[int]:
        res = []
        # 空节点
        if(len(xianxu) == 0): 
            return res
        # 建树
        root = self.buildTree(xianxu, 0, len(xianxu) - 1, zhongxu, 0, len(zhongxu) - 1)
        # 找每一层最右边的节点
        return self.rightSideView(root)

复杂度分析：

• 时间复杂度：$O(n^2)O(n^2)$，建树部分递归为$O(n)O(n)$，中序遍历中寻找根节点最坏$O(n)O(n)$，dfs每个节点访问一遍$O(n)O(n)$，故为$O(n^2)O(n^2)$
• 空间复杂度：$O(n)O(n)$，递归栈、哈希表、栈的空间都为$O(n)O(n)$

方法二：哈希表优化的递归建树+层次遍历(扩展思路)

知识点1：队列

队列是一种仅支持在表尾进行插入操作、在表头进行删除操作的线性表，插入端称为队尾，删除端称为队首，因整体类似排队的队伍而得名。它满足先进先出的性质，元素入队即将新元素加在队列的尾，元素出队即将队首元素取出，它后一个作为新的队首。

知识点2：哈希表

哈希表是一种根据关键码（key）直接访问值（value）的一种数据结构。而这种直接访问意味着只要知道key就能在$O(1)O(1)$时间内得到value，因此哈希表常用来统计频率、快速检验某个元素是否出现过等。

思路：

对于方法一中每次要寻找中序遍历中的根节点很浪费时间，我们可以利用一个哈希表直接将中序遍历的元素与前序遍历中的下标做一个映射，后续查找中序根节点便可以直接访问了。 同时除了深度优先搜索可以找最右节点，我们也可以利用层次遍历，借助队列，找到每一层的最右。值得注意的是：**每进入一层，队列中的元素个数就是该层的节点数。**因为在上一层他们的父节点将它们加入队列中的，父节点访问完之后，刚好就是这一层的所有节点。

具体做法：

• step 1：首先检查两个遍历序列的大小，若是为0，则空树不用打印。
• step 2：遍历前序遍历序列，用哈希表将中序遍历中的数值与前序遍历的下标建立映射。
• step 3：按照方法一递归划分子树，只是可以利用哈希表直接在中序遍历中定位根节点的位置。
• step 4：建立队列辅助层次遍历，根节点先进队。
• step 5：用一个size变量，每次进入一层的时候记录当前队列大小，等到size为0时，便到了最右边，记录下该节点元素。

Java实现代码：

import java.util.*;
public class Solution {
    public Map<Integer, Integer> index;
    //建树函数
    //四个int参数分别是前序最左节点下标，前序最右节点下标
    //中序最左节点下标，中序最右节点坐标
    public TreeNode buildTree(int[] xianxu, int l1, int r1, int[] zhongxu, int l2, int r2){
        if(l1 > r1 || l2 > r2)
            return null;
        //前序遍历中的第一个节点就是根节点
        int xianxu_root = l1;
        //在中序遍历中定位根节点
        int zhongxu_root = index.get(xianxu[xianxu_root]);
        TreeNode root = new TreeNode(xianxu[xianxu_root]);
        //得到左子树中的节点数目
        int leftsize = zhongxu_root - l2;
        root.left = buildTree(xianxu, l1 + 1, l1 + leftsize, zhongxu, l2, zhongxu_root - 1);
        root.right = buildTree(xianxu, l1 + leftsize + 1, r1, zhongxu, zhongxu_root + 1, r2);
        return root;
    }
    //层次遍历
    public ArrayList<Integer> rightSideView(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.offer(root);
        while(!q.isEmpty()){
            //队列中的大小即是这一层的节点树
            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);
                //最右元素
                if(size == 0) 
                    res.add(temp.val);
            }
        }
        return res;
    }
    
    public int[] solve (int[] xianxu, int[] zhongxu) {
        index = new HashMap<Integer, Integer>();
        //空节点
        if(xianxu.length == 0) 
            return new int[0];
        //用哈希表标记中序节点在前序中的位置
        for(int i = 0; i < xianxu.length; i++) 
            index.put(zhongxu[i], i);
        //建树
        TreeNode root = buildTree(xianxu, 0, xianxu.length - 1, zhongxu, 0, zhongxu.length - 1);
        //获取右视图输出
        ArrayList<Integer> temp = rightSideView(root);
        //转化为数组
        int[] res = new int[temp.size()]; 
        for(int i = 0; i < temp.size(); i++)
            res[i] = temp.get(i);
        return res;
    }
}

C++实现代码：

class Solution {
public:
    unordered_map<int, int> index;
    //建树函数
    //四个int参数分别是前序最左节点下标，前序最右节点下标
    //中序最左节点下标，中序最右节点坐标
    TreeNode* buildTree(vector<int>& xianxu, int l1, int r1, vector<int>& zhongxu, int l2, int r2) 
    {
        if(l1 > r1 || l2 > r2)
            return NULL;
        //前序遍历中的第一个节点就是根节点
        int xianxu_root = l1;
        //在中序遍历中定位根节点
        int zhongxu_root = index[xianxu[xianxu_root]];
        TreeNode* root = new TreeNode(xianxu[xianxu_root]);
        //得到左子树中的节点数目
        int leftsize = zhongxu_root - l2;
        root->left = buildTree(xianxu, l1 + 1, l1 + leftsize, zhongxu, l2, zhongxu_root - 1);
        root->right = buildTree(xianxu, l1 + leftsize + 1, r1, zhongxu, zhongxu_root + 1, r2);
        return root;
    }
    //层次遍历
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            //队列中的大小即是这一层的节点树
            int size = q.size(); 
            while(size--){
                TreeNode* temp = q.front();
                q.pop();              
                if(temp->left) 
                    q.push(temp->left);
                if(temp->right) 
                    q.push(temp->right);
                //最右元素
                if(size == 0) 
                    res.push_back(temp->val);
            }
        }
        return res;
    }
    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
        vector<int> res;
        //空节点
        if(xianxu.size() == 0) 
            return res;
        for(int i = 0; i < xianxu.size(); i++)
            index[zhongxu[i]] = i;
        //建树
        TreeNode* root = buildTree(xianxu, 0, xianxu.size() - 1, zhongxu, 0, zhongxu.size() - 1);
        //找每一层最右边的节点
        return rightSideView(root);
    }
};

Python实现代码

class Solution:
    index = defaultdict(int)
    # 建树函数
    # 四个int参数分别是前序最左节点下标，前序最右节点下标
    # 中序最左节点下标，中序最右节点坐标
    def buildTree(self, xianxu: List[int], l1: int, r1: int, zhongxu: List[int], l2: int, r2:int) -> TreeNode:
        if l1 > r1 or l2 > r2:
            return None
        # 前序遍历中的第一个节点就是根节点
        xianxu_root = l1 
        # 在中序遍历中定位根节点
        zhongxu_root = self.index[xianxu[xianxu_root]] 
        root = TreeNode(xianxu[xianxu_root])
        # 得到左子树中的节点数目
        leftsize = zhongxu_root - l2 
        root.left = self.buildTree(xianxu, l1 + 1, l1 + leftsize, zhongxu, l2, zhongxu_root - 1)
        root.right = self.buildTree(xianxu, l1 + leftsize + 1, r1, zhongxu, zhongxu_root + 1, r2)
        return root
    
    #层次遍历
    def rightSideView(self, root: TreeNode) -> List[int]:
        res = []
        q = queue.Queue()
        q.put(root)
        while not q.empty():
            #队列中的大小即是这一层的节点树
            size = q.qsize()
            while size:
                size -= 1
                temp = q.get()
                if temp.left:
                    q.put(temp.left)
                if temp.right:
                    q.put(temp.right)
                /#最右元素
                if size == 0:
                    res.append(temp.val)
        return res
    
    def solve(self , xianxu: List[int], zhongxu: List[int]) -> List[int]:
        res = []
        # 空节点
        if len(xianxu) == 0: 
            return res
        for i in range(len(xianxu)):
            self.index[zhongxu[i]] = i
        # 建树
        root = self.buildTree(xianxu, 0, len(xianxu) - 1, zhongxu, 0, len(zhongxu) - 1)
        # 找每一层最右边的节点
        return self.rightSideView(root)

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为二叉树节点个数，每个节点访问一次，哈希表直接访问数组中的元素
• 空间复杂度：$O(n)O(n)$，递归栈深度、哈希表、队列的空间都为$O(n)O(n)$