XO
BAN USERI went through your alg. and I got your idea but I do not think your algo works in O(n) time, though I am not quite sure about my view.
Your algo runs based on a hop step which start at A[0] and A[1]->A[2]->A[3]->A[5]->A[7]->....>A[2N-1]->A[2N-3]->....
You mark the element with a special value(nagative number in your example) to track which elements moved. And when your to_index points to an element which is moved(positive in your example), the to_index still need to point to next negative element:
to_index = index of next negative element.
This step I think is also a loop based on the number of N cuz you need to travel the array until the negative and I think, where I am not sure here, it also cost (N) time. So in this case, the upper bound of time also is O(N^2), not O(N)......
Does this make sense?
I think the original one:
isTreeBilateral(root->left, root1->right) && isTreeBilateral(root->right, root1->left) is more likely valid.
Cuz we suppose the "mirror" stands for the left of the left should be opposite the right of the right. root refers to left and root1 refers to right.
Am I right? This code sounds good but I am not pretty sure....I'd better run it this evening to make sure...
for the 1st approch, how you could write tree nodes into array like what you say, in other word, when you stop your scan on the tree. In your example, you used level-order. The issuse is how could you know -1 on the 15th position is the last one of the tree....
- XO February 10, 2011For the 2nd approach, preorder/inorder/postorder would have the same problem. You cannot tell whether a particular number is left or right or cousin's child. If you mark as NULL, how to stop your scan,i.e, how could you make sure there is no other valid nodes in a deeper level.