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

#include <cassert>
#include <queue>
class Solution {
    TreeNode *build_tree(
        vector<int> &preOrder,
        int preOrderLh,
        vector<int> &inOrder,
        int inOrderLh,
        int treeSize
    ) {
        if(treeSize == 0) {
            return nullptr;
        }

        int rootVal = preOrder[preOrderLh];
        int leftTreeSize = 0;
        for(int i = 0;i < treeSize; ++i) {
            if(inOrder[inOrderLh + i] == rootVal) {
                leftTreeSize = i;
                break;
            }
        }

        auto leftTree = build_tree(
            preOrder,
            preOrderLh + 1,
            inOrder,
            inOrderLh,
            leftTreeSize
        );
        auto rightTree = build_tree(
            preOrder,
            preOrderLh + 1 + leftTreeSize,
            inOrder,
            inOrderLh + leftTreeSize + 1,
            treeSize - leftTreeSize - 1
        );

        auto rootNode = new TreeNode(rootVal);
        rootNode->left = leftTree;
        rootNode->right = rightTree;
        return rootNode;
    }
public:
    struct NodeWrapper {
        TreeNode *node;
        int level;

        NodeWrapper(TreeNode *node, int level) {
            this->node = node;
            this->level = level;
        }
    };

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

        auto tree = build_tree(
            preOrder,
            0,
            inOrder,
            0,
            size
        );

        // level traverse
        queue<NodeWrapper> qu;
        qu.push(NodeWrapper(tree, 0));
        int last_level = 0;
        int last_val;
        vector<int> result;

        while(!qu.empty()) {
            auto node_wrapper = qu.front();
            qu.pop();
            
            if(node_wrapper.level != last_level) {
                // enter a new level
                result.push_back(last_val);
            }

            last_level = node_wrapper.level;
            last_val = node_wrapper.node->val;

            if(node_wrapper.node->left) {
                qu.push(NodeWrapper(node_wrapper.node->left, last_level + 1));
            }
            if(node_wrapper.node->right) {
                qu.push(NodeWrapper(node_wrapper.node->right, last_level + 1));
            }
        }

        // last level
        result.push_back(last_val);

        return result;
        
    }
};

分两步：构建树、层次遍历

这种分两步的算法题一定要进行单元测试，逐个保证每个模块的正确性，不然出错都不知是哪个环节