根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。
例如,给出
前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
和上一题基本一样0.0
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* build(vector<int>& preorder, vector<int>& inorder) {
TreeNode* tree = new TreeNode(preorder[0]);
if (inorder.size() <= 1) {
return tree;
}
int i, m;
for (i = 0; i < inorder.size(); i++) {
if (inorder[i] == preorder[0]) {
break;
}
}
m = i;
vector<int> arr0, arr1, brr0, brr1;
if (m == 0) {
tree->left = NULL;
}
else {
for (int j = 0, i = 1; j < m; j++, i++) {
arr0.push_back(preorder[i]);
brr0.push_back(inorder[j]);
}
tree->left = build(arr0, brr0);
}
if (m >= inorder.size() - 1) {
tree->right = NULL;
}
else {
for (int j = m + 1; j < inorder.size(); j++) {
arr1.push_back(preorder[j]);
brr1.push_back(inorder[j]);
}
tree->right = build(arr1, brr1);
}
return tree;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (inorder.size() == 0 || preorder.size() == 0) {
return NULL;
}
return build(preorder, inorder);
}
};
上面的代码可以通过此题,但是运行时间太长,因为每次传的都是一个数组,数组进行了大量的push操作导致变慢。可以记录下新创建数组的数的位置,就不传数组了,可以快一点
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
private:
vector<int> arr, brr;
public:
TreeNode *build(int a_0, int a_1, int b_0, int b_1)
{
TreeNode *tree = new TreeNode(arr[a_0]);
int i;
int lefta_0, lefta_1, leftb_0, leftb_1, righta_0, righta_1, rightb_0, rightb_1;
for (i = b_0; brr[i] != arr[a_0]; i++)
{
}
lefta_0 = a_0 + 1;
lefta_1 = a_0 + i - b_0;
leftb_0 = b_0;
leftb_1 = i - 1;
righta_0 = lefta_1 + 1;
righta_1 = a_1;
rightb_0 = i + 1;
rightb_1 = b_1;
if (i == b_0)
tree->left = NULL;
else
tree->left = build(lefta_0, lefta_1, leftb_0, leftb_1);
if (i == b_1)
tree->right = NULL;
else
tree->right = build(righta_0, righta_1, rightb_0, rightb_1);
return tree;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (inorder.size() == 0 || preorder.size() == 0) {
return NULL;
}
arr = preorder;
brr = inorder;
return build(0, arr.size() - 1, 0, brr.size() - 1);
}
};