题解 | #重建二叉树#
重建二叉树
https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ #include <cmath> #include <vector> class Solution { public: TreeNode* reConstructBinaryTreeFunction(vector<int> pre,vector<int> vin, int pre_low,int pre_high, int vin_low, int vin_high){ if(pre_high < pre_low || vin_low > vin_high) return nullptr; TreeNode* root = new TreeNode(pre[pre_low]); int mid = vin_low; for(int i = vin_low; i <= vin_high; i++){ if(root->val == vin[i]) { mid = i; break; } } root->left = reConstructBinaryTreeFunction(pre, vin, pre_low + 1, pre_low + mid - vin_low, vin_low, mid - 1); root->right = reConstructBinaryTreeFunction(pre, vin, pre_low + mid - vin_low + 1, pre_high, mid + 1, vin_high); return root; } TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) { return reConstructBinaryTreeFunction(pre, vin, 0, pre.size() - 1, 0, vin.size() - 1); } };