题解 | #重建二叉树#
重建二叉树
https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param preOrder int整型vector * @param vinOrder int整型vector * @return TreeNode类 */ TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) { // write code here if (preOrder.size() == 0){ return nullptr; } int father = preOrder[0]; //根节点在先序的首位(后序的末尾) TreeNode* root = new TreeNode(father); //新键本层的根节点 if (preOrder.size() == 1){ return root; } int index; //根节点在中序的位置 for (int i = 0; i < vinOrder.size(); i++) { if (vinOrder[i] == father) { index = i; } } //递归,左右子树进行构造 vector<int>preOrder_left (preOrder.begin() + 1, preOrder.begin() + 1 + index); //构造函数是[) 左开右闭 vector<int>preOrder_right (preOrder.begin() + 1 + index, preOrder.end()); vector<int>vinOrder_left (vinOrder.begin(), vinOrder.begin() + index); //构造函数是[) vector<int>vinOrder_right (vinOrder.begin() + index + 1, vinOrder.end()); root -> left = reConstructBinaryTree(preOrder_left, vinOrder_left); root -> right = reConstructBinaryTree(preOrder_right, vinOrder_right); return root; } };//改进:新创建vector比较耗时,可以使用数组下标