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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求二叉树的右视图
     * @param preOrder int整型vector 先序遍历
     * @param inOrder int整型vector 中序遍历
     * @return int整型vector
     */
    vector<int> res;
    struct node{
        node* left=nullptr;
        node* right=nullptr;
        int val=0;
        node(int _val):val(_val){}
        node(int _val, node* _left, node* _right):left(_left),right(_right),val(_val){}
    };

     //先序遍历得到根节点，然后在中序遍历中找到根节点、左子树、右子树，返回一层中最右的子树的根节点
    vector<int> solve(vector<int>& preOrder, vector<int>& inOrder) {
        if(preOrder.empty())return {};
        
        node* root = rebuild(preOrder, inOrder, 0, preOrder.size()-1, 0, inOrder.size()-1);

        queue<node*> q;
        q.push(root);

        int size = 1;
        while(!q.empty()){
            res.push_back(q.front()->val);  //放下一层右边第一个节点
            int new_size = 0;

            while(size > 0){ //排出当前层，放入下一层
                node* temp = q.front();q.pop();

                if(temp->right != nullptr){
                    q.push(temp->right);
                    new_size++;
                }  //非空的放入
                if(temp->left != nullptr){
                    q.push(temp->left);
                    new_size++;
                }

                --size;
            }

            size = new_size;
        }
    
        return res;
    }

    //重建二叉树，前序遍历数组的头一个是根节点，在中序遍历中找到根节点，通过下标计算出左右子树的大小，然后确定前序遍历数组中的左子树和右子树的范围，递归得对子树划分；
    node* rebuild(vector<int>& preOrder, vector<int>& inOrder, int pre_front_idx, int pre_back_idx, int in_front_idx, int in_back_idx){  
        if(pre_front_idx > pre_back_idx){
            return nullptr;
        }

        if(pre_front_idx == pre_back_idx){
            return new node(preOrder[pre_back_idx]); 
        }

        auto it = find(inOrder.begin()+in_front_idx, inOrder.begin()+in_back_idx, preOrder[pre_front_idx]);
        //string有find方法找到下标：s.find(num); vector没有。只有函数，返回迭代器；
        int root_idx = distance(inOrder.begin(), it);  //找到下标

        int left_sz = root_idx - in_front_idx;  //左子树有多少个
        int right_sz = in_back_idx - root_idx;  //右子树有多少个

        node* left_node = rebuild(preOrder, inOrder, pre_front_idx+1, pre_front_idx +left_sz , in_front_idx, root_idx-1);
        node* right_node = rebuild(preOrder, inOrder, pre_back_idx-right_sz+1, pre_back_idx, root_idx+1, in_back_idx);

        return new node(*it, left_node, right_node);
    }
};