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

最捞的一集，分步骤求解😅求右视图用逆序的层序遍历，可以节省一点时间。

#include <cstddef>
class Solution {
  public:
    bool areAllEmpty(const vector<TreeNode*>& vec) {
        for (int i = 0; i < vec.size(); i++) {
            if (vec[i]) return false;
        }
        return true;
    }
    TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {
        if (preOrder.empty() || vinOrder.empty()) return NULL;
        TreeNode* root = new TreeNode(preOrder[0]);
        int i;
        for (i = 0; i < vinOrder.size(); i++) {
            if (vinOrder[i] == root->val) break;
        }
        if (i) {
            vector<int> leftpre(preOrder.begin() + 1, preOrder.begin() + i + 1);
            vector<int> leftvin(vinOrder.begin(), vinOrder.begin() + i);
            root->left = reConstructBinaryTree(leftpre, leftvin);
        } else {
            root->left = NULL;
        }
        if (i < vinOrder.size() - 1) {
            vector<int> rightpre(preOrder.begin() + i + 1, preOrder.end());
            vector<int> rightvin(vinOrder.begin() + i + 1, vinOrder.end());
            root->right = reConstructBinaryTree(rightpre, rightvin);
        } else {
            root->right = NULL;
        }

        return root;
    }
    vector<int> solve(vector<int>& preOrder, vector<int>& inOrder) {
        TreeNode* root = reConstructBinaryTree(preOrder, inOrder);
        vector<int> res;
        if (!root) return res;
        vector<TreeNode*> query;
        query.push_back(root);
        TreeNode* tmp;
        int depth = 0;
        while (!query.empty()) {
            if (areAllEmpty(query)) break;
            if (query.size() == pow(2, depth)) {
                for (int i = 0; i < query.size(); i++) {
                    if (query[i] != NULL) {
                        res.push_back(query[i]->val);
                        break;
                    }
                }
                depth++;
            }
            tmp = query[0];
            if (tmp) {
                query.push_back(tmp->right);
                query.push_back(tmp->left);
            } else {
                query.push_back(nullptr);
                query.push_back(nullptr);
            }
            query.erase(query.begin());
        }
        return res;
    }
};