[数据结构与算法]输出二叉树的右视图--CPP实现

描述

请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图

思路：

1、根据先序和后序遍历结果，反推二叉树（还原为为二叉树）

2、层序遍历树，输出每一层的最右面的元素

3、返回

class Solution {
public:
    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
        // write code here
         TreeNode* root = reBuildBST(xianxu, zhongxu);
        vector<int> res;
 
        // 层序遍历收集二叉树的右视图的节点的值
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()) {
            int size = que.size();
            TreeNode* node = nullptr;
            while(size--) {
                node = que.front(); que.pop();
                if(node->left)    que.push(node->left);
                if(node->right)    que.push(node->right);
            }
            if(node)
                res.push_back(node->val);
        }
         return res;
    }
    
    // 重建二叉树
    TreeNode* reBuildBST(vector<int>& xianxu, vector<int>& zhongxu) {
        if(xianxu.size()==0 || zhongxu.size()==0)
            return nullptr;
 
        int rootVal = xianxu[0];
        TreeNode* root = new TreeNode(rootVal);
 
        int index = 0;
        while(index < zhongxu.size()) {
            if(zhongxu[index] == rootVal)
                break;
            index ++;
        }
 
        vector<int> lzhongxu(zhongxu.begin(), zhongxu.begin()+index);
        vector<int> rzhongxu(zhongxu.begin()+index+1, zhongxu.end());
 
        vector<int> lxianxu(xianxu.begin()+1, xianxu.begin()+1+index);
        vector<int> rxianxu(xianxu.begin()+1+index, xianxu.end());
 
        root->left = reBuildBST(lxianxu, lzhongxu);
        root->right = reBuildBST(rxianxu, rzhongxu);
 
        return root;
    }
    
};