题解 | #c++时间第一输出二叉树的右视图（还包括中序后序，左视图输出） #

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型vector 先序遍历
     * @param zhongxu int整型vector 中序遍历
     * @return int整型vector
     */
    /*  1.先序中序*/
    /*  2.中序后序*/
    /*  3.先煦后序*/
    /*
     * 思路：以一个遍历结果为序逐次创建根节点，然后递归搜索此节点的左子与右子
     * 示例：以中序创建根节点，递归搜索左右子节点
     */
    vector<int> result;
    /*中序先序 索引参数搞明白就行*/
    TreeNode* creat_by_zx(vector<int>& pre,vector<int>& mid,int next,int otherstart,
                          int otherend){
        if(otherstart > otherend){
            return nullptr;
        }else{int start = 0;
             TreeNode* curnode = new TreeNode(pre[next]);
              for(int i = otherstart;i<= otherend;i++){
                  if(curnode->val == mid[i]){
                      start = i;break;
                  }
              }
              curnode->left = creat_by_zx(pre, mid, next+1, otherstart, start-1);
              curnode->right = creat_by_zx(pre, mid, next+start-otherstart+1,start+1,otherend);
              return curnode;
        }
    }
    /*后序中序---类似中序先序，重点看递归的参数变化*/
    TreeNode* creat_by_hz(vector<int>& mid,vector<int>& last,int next,int otherstart,int otherend){
        if(otherstart>otherend){
            return nullptr;
        }else{
            TreeNode* curnode = new TreeNode(last[next]);int k = 0;
            for(int i = otherstart;i<=otherend;i++){
                if(mid[i] == curnode->val){
                    k = i;break;
                }
            }
            curnode->left = creat_by_hz(mid, last, next-(otherend-k)-1, otherstart, k-1);
            curnode->right = creat_by_hz(mid, last, next-1, k+1, otherend);
            return curnode;
        }
    }
  /*用于测试的dfs遍历函数 不用看*/
    void dfsserch(TreeNode* root,void anyfunction(TreeNode* p)){
        if(root == nullptr){
            return;
        }else{
            anyfunction(root);
            dfsserch(root->left, anyfunction);
            dfsserch(root->right, anyfunction);
        }
    }
    static void function(TreeNode* p){
        cout <<p->val<<",";
    }
  /*右视图*/
    vector<int> bfsserch(TreeNode* root){
        if(root == nullptr){
            return result;
        }else{
            queue<TreeNode*> Nodes;Nodes.push(root);
            while(!Nodes.empty()){
                int size = Nodes.size();
                while(size>0){
                    auto temp = Nodes.front();
                    Nodes.pop();
                    if(size == 1){
                      result.push_back(temp->val);
                    }
                    size--;
                    if(temp->left){
                        Nodes.push(temp->left);
                    }if(temp->right){
                        Nodes.push(temp->right);
                    }
                }
            }
            return result;
        }
    }
  /*左视图 看了右视图就不用看这个了 类似*/
    vector<int> bfsserch1(TreeNode* root){
        if(root == nullptr){
            return result;
        }else{
            queue<TreeNode*> Nodes;Nodes.push(root);
            while(!Nodes.empty()){
                int size = Nodes.size();
                while(size>0){
                    auto temp = Nodes.front();
                    Nodes.pop();
                    if(size == 1){
                        result.push_back(temp->val);
                    }size--;if(temp->right){
                        Nodes.push(temp->right);
                    }if(temp->left){
                        Nodes.push(temp->left);
                    }
                }
            }
            return result;
        }
    }
    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
        // write code here
        //恢复二叉树 -- 先序中序
        TreeNode* root = creat_by_zx(xianxu, zhongxu,0, 0, zhongxu.size()-1);
        //恢复二叉树 -- 中序后序
        //TreeNode* root = creat_by_hz(houxu, zhongxu,houxu.size()-1, 0, zhongxu.size()-1);
        dfsserch(root, function);
        /*左视图 -- broad frist serch
        bfsserch1(root);
        result.clear();
        */
        //右视图 -- broad frist serch
        return bfsserch(root);
    }
};