题解 | 输出二叉树的右视图
输出二叉树的右视图
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; } };
分两步:构建树、层次遍历
这种分两步的算法题一定要进行单元测试,逐个保证每个模块的正确性,不然出错都不知是哪个环节