题解 | #重建二叉树#
重建二叉树
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) {} * }; */ class Solution { public: TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) { if (preOrder.empty() || vinOrder.empty()) return nullptr; //前序的第一个是根节点 int rootVal = preOrder[0]; TreeNode* pRoot = new TreeNode(rootVal); // 在中序遍历中找到根节点的位置 auto it = std::find(vinOrder.begin(), vinOrder.end(), rootVal); int rootIndex = it - vinOrder.begin(); // 构建左子树的前序和中序遍历序列 std::vector<int> leftPreOrder(preOrder.begin() + 1, preOrder.begin() + 1 + rootIndex); std::vector<int> leftVinOrder(vinOrder.begin(), vinOrder.begin() + rootIndex); // 构建右子树的前序和中序遍历序列 std::vector<int> rightPreOrder(preOrder.begin() + 1 + rootIndex, preOrder.end()); std::vector<int> rightVinOrder(vinOrder.begin() + rootIndex + 1, vinOrder.end()); // 递归构建左右子树 pRoot->left = reConstructBinaryTree(leftPreOrder, leftVinOrder); pRoot->right = reConstructBinaryTree(rightPreOrder, rightVinOrder); return pRoot; } };