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

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// struct TreeNode{
//     int val;
//     TreeNode* left;
//     TreeNode* right;
// }


class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型vector 先序遍历
     * @param zhongxu int整型vector 中序遍历
     * @return int整型vector
     */
    TreeNode* buildTree(vector<int>& pre,vector<int>& vin){
        int n = pre.size();
        int m = vin.size();
        if(m == 0 || n == 0) return nullptr;
        TreeNode* p = new TreeNode(pre[0]);
        for(int i = 0;i < m;i ++){
            if(pre[0] == vin[i]){
                vector<int> leftPre(pre.begin() + 1,pre.begin() + 1 + i);
                vector<int> leftVin(vin.begin(),vin.begin() + i);
                p -> left = buildTree(leftPre,leftVin);
                vector<int> rightPre(pre.begin() + 1 + i,pre.end());
                vector<int> rightVin(vin.begin() + 1 + i,vin.end());
                p -> right = buildTree(rightPre,rightVin);
                break;
            }
        }
        return p;
    }   

    vector<int> findRight(TreeNode* proot){
        vector<int> res;
        if(!proot) return res;
        queue<TreeNode*> q;
        q.push(proot);
        while(!q.empty()){
            int right = 0;
            int length = q.size();
            for(int i = 0;i < length;i ++){
                if(q.front() -> left) q.push(q.front() -> left);
                if(q.front() -> right) q.push(q.front() -> right);
                right = q.front() -> val;
                q.pop();
            }
            res.push_back(right);
        }
        return res;
    }

    void printTree(TreeNode* proot){
        if(proot == nullptr) return;
        //cout << proot -> val << " ";
        printTree(proot -> left);
        printTree(proot -> right);
    }

    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
        // write code here
        vector<int> res;
        if(xianxu.size() != zhongxu.size() || xianxu.size() == 0 || zhongxu.size() == 0){
            return res;
        }
        TreeNode* tree = new TreeNode(0);
        tree = buildTree(xianxu,zhongxu);
        printTree(tree);
        res = findRight(tree);
        return res;
    }
};

经过这几天的刷题，由自己不开代码补全做出来的。还是有进步。

就是融合了重建二叉树和层次遍历的一道题。

记录一下。