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

思路：

题目的主要信息：

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

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

建树
打印右视图

首先建树方面，先序遍历是根左右的顺序，中序遍历是左根右的顺序，因为节点值互不相同，我们可以根据在先序遍历中找到根节点（每个子树部分第一个就是），再在中序遍历中找到对应的值，从其左右分割开，左边就是该树的左子树，右边就是该树的右子树，于是将问题划分为了子问题。
图片说明
打印右视图即找到二叉树每层最右边的结点元素，我们可以采取dfs或者bfs两种方式遍历树，根据记录的深度找到最右值。

方法一：递归建树+深度优先搜索
具体做法：
建树函数根据上述说的划分，可以使用递归解决，利用l1 r1 l2 r2分别记录子树部分在数组中分别对应的下标，并跟随函数进行递归。
dfs部分，采用两个栈，一个栈记录深度优先搜索结点的次序，一个栈记录与前者相应的深度，另利用一个哈希表来记录每层的最右的结点，因为结点值不重复，因此哈希表很适应。因为dfs是先序遍历的，根左右的顺序，因此同一层中后访问的必然是更右边的结点，因此按照顺序每次更新哈希表即可。

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; //维护深度访问结点
        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);
    }
};

复杂度分析：

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

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

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);
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，每个结点访问一次，哈希表直接访问
空间复杂度： $O(n)$ ，递归栈深度、哈希表、队列的空间都为 $O(n)$