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

#include <functional>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型vector 先序遍历
     * @param zhongxu int整型vector 中序遍历
     * @return int整型vector
     */
    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
        vector<int> result(10000);
        int maxlayer = 0;
        function<void(int, int, int, int, int)> dfs = [&](int xl, int xr, int zl, int zr, int layer) -> void {
            if (xl > xr) {
                return;
            }
            maxlayer = max(maxlayer, layer);
            int base = xianxu[xl];
            result[layer] = base;
            int zm = zl;
            while (zhongxu[zm] != base) {
                ++zm;
            }
            dfs(xl + 1, xl + zm - zl, zl, zm - 1, layer + 1);
            dfs(xl + zm - zl + 1, xr, zm + 1, zr, layer + 1);
        };
        dfs(0, xianxu.size() - 1, 0, zhongxu.size() - 1, 0);
        result.resize(maxlayer + 1);
        return result;
    }
};

思路：把这个问题分成两部分。

第一部分：根据先序和中序构造二叉树。有一道原题，直接递归构造即可。

第二部分：计算二叉树的右视图。

* 先序遍历：中-左-右，同时记录当前遍历的深度。

* 数组记录右视图，下标表示深度，下标上的元素表示该深度的最右元素。

* 因为先序遍历，所以对于数组中每个位置（相同深度的节点），树中左边的元素会被右边的元素覆盖，最后一定会得到最右元素。

结合：

* 第一部分实际上就是一个先序遍历的过程。（先找到根节点，再根据根节点区分开左右子树，然后对左右子树递归）

* 所以，在第一部分找到根节点时，记录到数组中的对应位置即可。