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

输出二叉树的右视图

https://www.nowcoder.com/practice/c9480213597e45f4807880c763ddd5f0

#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;
        
    }
};

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

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

全部评论

相关推荐

03-31 18:02
门头沟学院 Java
白日梦想家_等打包版:不要的哦佛给我
点赞 评论 收藏
分享
爱吃肉的伊登在写日记:好棒,27届简历能做成这个样子,但是第一个项目感觉cover住难度还是不小的,特别是二面的时候肯定要对分布式系统设计这一块儿有高出正常面试者的水平才行
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务