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

#include <deque>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求二叉树的右视图
     * @param preOrder int整型vector 先序遍历
     * @param inOrder int整型vector 中序遍历
     * @return int整型vector
     */

    // 恢复二叉树
    TreeNode* dfs(vector<int>& preOrder, vector<int>& inOrder)
    {
        int len_p=preOrder.size();
        int len_i=inOrder.size();

        if(len_p==0 || len_i==0)
            return nullptr;
        
        // 创建当前的根节点
        TreeNode* root = new TreeNode(preOrder[0]);

        for(int i=0; i<len_i; ++i)
        {
            // 找到根节点在中序遍历中的位置i，然后i其实就是前序遍历中左子树最后的节点的位置;
            if(inOrder[i] == preOrder[0])
            {
                // 左子树的前序遍历
                vector<int> f_p(preOrder.begin()+1,preOrder.begin()+i+1);
                // 左子树的中序遍历
                vector<int> f_i(inOrder.begin(),inOrder.begin()+i);
                // 当前根节点的左子树
                root->left = dfs(f_p,f_i);

                // 右子树的前序遍历
                vector<int> r_p(preOrder.begin()+i+1,preOrder.end());
                // 右子树的中序遍历
                vector<int> r_i(inOrder.begin()+i+1,inOrder.end());
                // 当前根节点的右子树
                root->right = dfs(r_p,r_i);

                break;
            }
        }

            return root;
    }


    vector<int> solve(vector<int>& preOrder, vector<int>& inOrder) {
        // write code here

        TreeNode* root = dfs(preOrder,inOrder);

        // 广度优先搜索
        vector<int> ans;
        deque<TreeNode*> d;
        d.emplace_back(root);
        
        while(!d.empty())
        {
            int len = d.size();
            for(int i=0 ;i<len; ++i)
            {
                if(i==len-1)
                    ans.emplace_back(d.front()->val);

                if(d.front()->left)
                    d.emplace_back(d.front()->left);

                if(d.front()->right)
                    d.emplace_back(d.front()->right);

                d.pop_front();
            }
        }

        return ans;
    }
};