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

方法：递归、BFS（层序遍历）

二叉树的右视图就是二叉树每一层的最右结点。

具体方法：

1、利用递归使用前序和中序遍历重建二叉树；

2、对重建后的二叉树进行层序遍历，将每一层的最后一个元素存入数组中，层序遍历完成后就得到二叉树的右视图

时间复杂度：o(n)

空间复杂度：o(n)

class Solution {
  public:
    TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {
        if (preOrder.size() == 0 || vinOrder.size() == 0)
            return nullptr;
        TreeNode* head = new TreeNode(preOrder[0]);

        for (int i = 0; i < vinOrder.size(); i++) {
            if (vinOrder[i] == preOrder[0]) {
                //左子树
                vector<int> leftvin(vinOrder.begin(), vinOrder.begin() + i);
                vector<int> leftpre(preOrder.begin() + 1, preOrder.begin() + i + 1);
                head->left = reConstructBinaryTree(leftpre, leftvin);
                //右子树
                vector<int> rightvin(vinOrder.begin() + i + 1, vinOrder.end());
                vector<int> rightpre(preOrder.begin() + i + 1, preOrder.end());
                head->right = reConstructBinaryTree(rightpre, rightvin);
            }
        }

        return head;
    }
    vector<int> solve(vector<int>& preOrder, vector<int>& inOrder) {
        vector<int> right_tree;
        if (preOrder.size() == 0 || inOrder.size() == 0)
            return right_tree;

        //重建二叉树
        TreeNode* head = reConstructBinaryTree(preOrder, inOrder);

        queue<TreeNode*> temp;
        temp.push(head);
        //BFS
        while (temp.size()) {
            int length = temp.size();
            for (int i = 0; i < length; i++) {
                //每一层的最后一个元素保存下就是二叉树的右视图
                if (i == length - 1)
                    right_tree.push_back(temp.front()->val);
                if (temp.front()->left)
                    temp.push(temp.front()->left);
                if (temp.front()->right)
                    temp.push(temp.front()->right);
                temp.pop();
            }
        }
        return right_tree;
    }
};