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

#include <iostream>
#include <iterator>
#include <queue>
#include <strings.h>
#include <vector>
class Solution {
  public:
    TreeNode* constructBinTree(vector<int>& preOrder, vector<int>& inOrder) {
        if (preOrder.empty()) {
            return nullptr;
        }
        auto rootVal = preOrder[0];
        auto inOrderRootIndex = 0;
        for (int i = 0; i < inOrder.size(); i++) {
            if (inOrder[i] == rootVal) {
                inOrderRootIndex = i;
                break;
            }
        }
        auto root = new TreeNode(preOrder[0]);
        auto inOrder1 = std::vector<int>(inOrder.begin(),
                                         inOrder.begin() + inOrderRootIndex);
        auto inOrder2 = std::vector<int>(inOrder.begin() + inOrderRootIndex + 1,
                                         inOrder.end());
        auto preOrder1 = std::vector<int>(preOrder.begin() + 1,
                                          preOrder.begin() + inOrderRootIndex + 1);
        auto preOrder2 = std::vector<int>(preOrder.begin() + inOrderRootIndex + 1,
                                          preOrder.end());
        if (!inOrder1.empty()) {
            root->left = constructBinTree(preOrder1, inOrder1);
        }
        if (!inOrder2.empty()) {
            root->right = constructBinTree(preOrder2, inOrder2);
        }
        return root;
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求二叉树的右视图
     * @param preOrder int整型vector 先序遍历
     * @param inOrder int整型vector 中序遍历
     * @return int整型vector
     */
    vector<int> solve(vector<int>& preOrder, vector<int>& inOrder) {
        // write code here
        if (preOrder.empty()) {
            return preOrder;
        }
        std::vector<int> rigthViewNodeVals;
        auto root = constructBinTree(preOrder, inOrder);
        rigthViewNodeVals.push_back(root->val);
        queue<TreeNode*> fatherNodes;
        fatherNodes.push(root);
        int recordVal = 0;
        bool flag = false;
        while (!fatherNodes.empty()) {
            auto length = fatherNodes.size();
            for (int i = 0; i < length; i++) {
                if (fatherNodes.front()->left != nullptr) {
                    flag = true;
                    fatherNodes.push(fatherNodes.front()->left);
                    recordVal = fatherNodes.front()->left->val;
                    std::cout << recordVal << " " << endl;
                }
                if (fatherNodes.front()->right != nullptr) {
                    flag = true;
                    fatherNodes.push(fatherNodes.front()->right);
                    recordVal = fatherNodes.front()->right->val;
                    std::cout << recordVal << " " << endl;
                }
                fatherNodes.pop();
            }
            std::cout << "flag: "<< flag <<endl;
            if (flag) {
                rigthViewNodeVals.push_back(recordVal);
            }
            flag = false;
        }
        return rigthViewNodeVals;
    }
};