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

建树在二叉树的还原做过了。然后是右视图，采用层次遍历，每次取最后的数字压入数组。实际算法还可以优化，这里就先这样吧。

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型vector 先序遍历
     * @param zhongxu int整型vector 中序遍历
     * @return int整型vector
     */
    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
      if (xianxu.empty() || zhongxu.empty()) {
        return std::vector<int>();
      }

      TreeNode *root = restruct(xianxu, zhongxu);
      std::vector<int> res;
      std::queue<TreeNode *> tree;
      //  bool stop_flag = false;

      tree.push(root);
      res.push_back(root->val);

      while (!tree.empty()) {
        int size = tree.size();
        int val;

        for (int i = 0; i < size; ++i) {
          TreeNode *cur = tree.front();
          tree.pop();

          if (cur->left) {
            val = cur->left->val;
            tree.push(cur->left);
          }

          if (cur->right) {
            val = cur->right->val;
            tree.push(cur->right);
          }
        }

        if (val != *(res.end() - 1)) {
          res.push_back(val);
        }
      }

      return res;
    }
  private:
    TreeNode* restruct(const std::vector<int> &xianxu, const std::vector<int> &zhongxu) {
      if (xianxu.empty()) {
        return nullptr;
      }

      TreeNode *root = new TreeNode(xianxu[0]);

      auto p_fir = xianxu.begin();
      auto p_ord = zhongxu.begin();

      while (*p_ord != *p_fir) {
        ++p_ord;
      }

      p_fir = p_fir + (p_ord - zhongxu.begin()) + 1;

      root->left = restruct(std::vector<int>(xianxu.begin() + 1, p_fir), std::vector<int>(zhongxu.begin(), p_ord));
      root->right = restruct(std::vector<int>(p_fir, xianxu.end()), std::vector<int>(p_ord + 1, zhongxu.end()));

      return root;
    }
};