oohtj
BAN USERoooh, that's me, tj
My idea is similar to the Vincent above. You have to use the parent pointer to save the time complexity. The whole idea explains as followings:
1) when constructing the tree, each node saves these information:
value, left pointer, right pointer, and an additional parent pointer.
2) Use BFS trick to traversing the tree, and calculate the sum of path from root to current node. If the node:
a. has all child node(s) non-positive
b. has no child node
then store this node to the candidate array. (This is because that only these two types of node can be the maximum path.)
3. After the traverse, we found the maximum, then traverse the candidate array, and print the maximum path(s) following the parent link.
Note that the size of candidate array is smaller than N.
The total time complexity is O(N).
0 . since there is no memory limit, so we could take advantage of that.
support all the characters are ASCII chars, let char A[] = char[256];
and all clear to zero.
1. pre-process the given 5 words
use the char array A to hash the 5 words, and make 5 linked list, each node is a char and its occurence times. let these lists be L[5];
2 for each word w in the large, whole day word queue,
2.1 hash w into the array A and update the w's occurence
2.2 for each list L in the 5 lists
2.2.1 compare the word and occurence in each node
2.2.2 if found, output w
2.3 now we continue to the next w in the queue
The total time complexity is O(N*Mav), N is the length of queue, Mav is the average word length of queue. This method is faster than the STL method, you can bet on that. If you spotted any problem, feel free to contact me.
u r right. that's the bug. thank u a lot.
That's the fix:
1) from A, traverse up until encounter the node C
a. C is the root node
b. C with value between A and B
c. C is the destination, that's the answer
2) from C, if B is larger than C, do the binary search in its right child sub tree; otherwise, search in the left child sub tree
3) concatenate the path A->C->B, that's it.
Time complexity still holds as O(logN).
I have another solution:
Let given node be A, destination node be B
1) from A, traverse up following the pointer to parent until encounter three types of node, let the node be C
a. C is the root node
b. C with value bigger than the destination value
c. C node equals to the destination, then we got the path from A to B, return.
2) do the binary search on the right child tree of C to find B
3) If we find B, concatenate the path A -> C -> B, that's the answer.
The time complexity of this method is O(logN + logN) = O(logN)
I can not understand your question.
- oohtj May 13, 2013