w*******u
发帖数: 267 | 1 Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-
inorder-traversal/
————————————————————————————————————
我的解法
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder,
int inorderSize) {
if (preorderSize == 0) return NULL;
int rootVal = preorder[0];
int rootNodePos = -1;
for (int i = 0; i < inorderSize; i++) {
if (rootVal == inorder[i]) rootNodePos = i;
}
struct TreeNode *root = malloc(sizeof(struct TreeNode));
root->val = rootVal;
root->left = buildTree(preorder + 1, rootNodePos, inorder, rootNodePos);
root->right = buildTree(preorder + rootNodePos + 1, preorderSize -
rootNodePos - 1, inorder + rootNodePos + 1, inorderSize - rootNodePos - 1);
}
在leetcode上run了一下，要20ms,不是最优解。请问大虾们这道题如何得到最优解。谢
谢！！！ | b***e
发帖数: 1419 | 2 你这个是O(n^2)的算法。想要吧复杂度降到O(n)的话要先hash sort一下in order
sequence。 |
|
