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

class Solution {
public:
    vector<int> solve(vector<int>& preOrder, vector<int>& inOrder) {
        dfs(preOrder, inOrder, 0);
        return ans;
    }

private:
    vector<int> ans;
    
    void dfs(const vector<int>& preOrder, const vector<int>& inOrder, int depth)
    {
        if(preOrder.size() == 0) return;
        if(ans.size() == depth) ans.push_back(preOrder[0]);
        int idx = 0;
        for(int i =0; i < inOrder.size(); i++)
        {
            if(inOrder[i] == preOrder[0])
            {
                idx = i;
                break;
            }
        }

        dfs(vector<int>(preOrder.begin() + idx + 1, preOrder.end()),
        vector<int>(inOrder.begin() + idx + 1, inOrder.end()), depth + 1);
        dfs(vector<int>(preOrder.begin()+1, preOrder.begin() + idx + 1),
        vector<int>(inOrder.begin(), inOrder.begin() + idx), depth + 1);
    }
};

在递归重建时优先从右子树开始重建，如果首次到达新的一层记录节点即可