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

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求二叉树的右视图
     * @param preOrder int整型vector 先序遍历
     * @param inOrder int整型vector 中序遍历
     * @return int整型vector
     */

    TreeNode* fun(vector<int>& preOrder, vector<int>& vinOrder, int preBegin,
                  int preEnd, int vinBegin, int vinEnd) {
        if (vinBegin <= vinEnd) {
            TreeNode* root = new TreeNode(preOrder[preBegin]);
            int i = -1;
            for (i = vinBegin; i <= vinEnd; i++) {
                if (vinOrder[i] == preOrder[preBegin])
                    break;
            }
            int leftNum = i - vinBegin;
            int rightNum = vinEnd - i;
            root->left = fun(preOrder, vinOrder, preBegin + 1, preBegin + leftNum, vinBegin,
                             i - 1); // 有问题
            root->right = fun(preOrder, vinOrder, preBegin + leftNum + 1, preEnd, i + 1,
                              vinEnd);
            return root;
        }
        return nullptr;
    }

    vector<int> solve(vector<int>& preOrder, vector<int>& inOrder) {
        // write code here
        int size = preOrder.size();
        TreeNode* root = fun(preOrder,inOrder,0,size-1,0,size-1);
        // 用层次遍历来输出即可？ 每一层的最后一个元素即使所求
        vector<TreeNode*> queue(size+1);
        int front=-1,rear=-1,last=0;
        TreeNode* p =root;
        vector<int> vv;
        queue[++rear] = p;
        while(front<=rear)
        {
            p = queue[++front];
            if(!p)
                break;
            if(p->left)
                queue[++rear] = p->left;
            if(p->right)
                queue[++rear] = p->right;
            if(last == front)
            {
                vv.push_back(p->val);
                last=rear;
            }
        }
        return vv;
    }
};

核心思想：先建树，建树用递归的去建。先序第一个即为根，然后根据中序找出它左边有几个元素，右边有几个元素。

采用层次遍历，只有访问到每层的最后一个元素，则将其push_back进vv中。

注意queue应该开size+1个大小，因为退出的时候要保证front>rear。

并且vector默认初始化为nullptr，所以加一个if(!p) break; 即可退出循环。