题解 | #输出二叉树的右视图#
输出二叉树的右视图
https://www.nowcoder.com/practice/c9480213597e45f4807880c763ddd5f0
#include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 求二叉树的右视图 * @param preOrder int整型vector 先序遍历 * @param inOrder int整型vector 中序遍历 * @return int整型vector */ TreeNode* reConstructBinaryTreeFun(vector<int>& preOrder, vector<int>& vinOrder, int preBegin, int preEnd, int vinBegin, int vinEnd) { if (preOrder.empty() || vinOrder.empty()) return nullptr; auto root = new TreeNode(preOrder[preBegin]); if (preBegin == preEnd) return root; int index = vinBegin; while (index != vinEnd + 1 && vinOrder[index] != preOrder[preBegin]) { index++; } if (index == vinBegin) { root->right = reConstructBinaryTreeFun(preOrder, vinOrder, preBegin + 1, preEnd, vinBegin + 1, vinEnd); return root; } if (index == vinEnd) { root->left = reConstructBinaryTreeFun(preOrder, vinOrder, preBegin + 1, preEnd, vinBegin, vinEnd - 1); return root; } root->left = reConstructBinaryTreeFun(preOrder, vinOrder, preBegin + 1, preBegin + index - vinBegin, vinBegin, index - 1); root->right = reConstructBinaryTreeFun(preOrder, vinOrder, preBegin + index - vinBegin + 1, preEnd, index + 1, vinEnd); return root; } vector<int> solve(vector<int>& preOrder, vector<int>& inOrder) { // write code here TreeNode* root = reConstructBinaryTreeFun(preOrder, inOrder, 0, preOrder.size() - 1, 0, inOrder.size() - 1); if (root == nullptr) return {}; list<TreeNode*> li; vector<int> result; li.push_back(root); while (!li.empty()) { { int size = li.size(); while (size--) { if (size == 0) result.push_back(li.front()->val); if (li.front()->left) li.push_back(li.front()->left); if (li.front()->right) li.push_back(li.front()->right); li.pop_front(); } } } return result; }; };