题目描述

请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图
输入：[1,2,4,5,3],[4,2,5,1,3]
输出：[1,3,5]

//解析： 先重构二叉树  然后利用层次遍历的方式打印出二叉树的右子树
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型vector 先序遍历
     * @param zhongxu int整型vector 中序遍历
     * @return int整型vector
     */
    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
        // write code here
        if(xianxu.empty() || zhongxu.empty())
        {
            return {};
        }
        
        TreeNode* root = Construct(xianxu, zhongxu, 0, xianxu.size()-1, 0, zhongxu.size()-1);
        vector<int> res;
        
        queue<TreeNode*> q;
        q.push(root);
        //层次遍历 常用的算法可以记住
        while(!q.empty())
        {
            int len = q.size();
            TreeNode* t = q.front();
            res.push_back(t->val);
            while(len--)
            {
                t = q.front();
                q.pop();
                if(t->right)
                {
                    q.push(t->right);
                }
                if(t->left)
                {
                    q.push(t->left);
                }
            }
        }
        
        return res;
    }
    
    TreeNode* Construct(vector<int> pre, vector<int> vin, int pl, int pr, int vl, int vr)
    {
        if(pl > pr || vl > vr)
        {
            return nullptr;
        }
        
        //找到跟节点的索引
        int size = 0;
        for(int i = vl; i <= vr; i++)
        {
            if(vin[i] == pre[pl])
            {
                size = i - vl;
                break;
            }
        }
        
        //利用递归重构二叉树
        TreeNode* root = new TreeNode(pre[pl]);
        root->left = Construct(pre, vin, pl+1, pl+size, vl, vl+size-1);
        root->right = Construct(pre, vin, pl+size+1, pr, vl+size+1, vr);
        
        return root;
    }
};