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

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求二叉树的右视图
     * @param preOrder int整型vector 先序遍历
     * @param inOrder int整型vector 中序遍历
     * @return int整型vector
     */
    vector<int> solve(vector<int>& preOrder, vector<int>& inOrder) {
        // write code here
        vector<int> result;
        result.clear();
        if( preOrder.size() == 0 || inOrder.size() == 0 ) return result;
        TreeNode* head = buildTree(preOrder, inOrder);
        return bfs(head, result);
    }

    TreeNode* buildTree( vector<int>& preOrder, vector<int>& inOrder )
    {
        if(preOrder.size() == 0) return nullptr;
        int rootVal = preOrder.front();
        TreeNode* root = new TreeNode(rootVal);
        int index = 0;
        for( int i = 0; i < inOrder.size(); i++ )
        {
            if(inOrder[i] == rootVal)
            {
                index = i;
                break;
            }
        }
        vector<int> leftinOrder = vector<int>( inOrder.begin(), inOrder.begin() + index );
        vector<int> rightinOrder = vector<int>( inOrder.begin() + index + 1, inOrder.end() );
        int size = leftinOrder.size();

        preOrder.erase(preOrder.begin());
        vector<int> leftpreOrder = vector<int>( preOrder.begin(), preOrder.begin() + size );
        vector<int> rightpreOrder = vector<int>( preOrder.begin() + size, preOrder.end() );
        root->left = buildTree( leftpreOrder, leftinOrder );
        root->right = buildTree( rightpreOrder, rightinOrder );
        return root;
    }

    vector<int> bfs( TreeNode* head, vector<int>& result )
    {
        if(head == nullptr) return result;
        queue<TreeNode*> q;
        q.push(head);
        while(!q.empty())
        {   int size = q.size();
            for( int i = 0; i < size; i++ )
            {
                TreeNode* cur = q.front();
                q.pop();
                if( i == size - 1 )
                {
                    result.push_back(cur->val);
                }
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            }
        }
        return result;
    }

};