crdmp
BAN USERI think alternate = !alternate should be outside the inner while loop because alternate should only change once you start a new level, not after each processed node.
Also, reversing the children of a node isn't enough. You have to reverse the whole level. Because of this, I think it's necessary to use a stack inside the inner while loop.
Of course, I might be wrong but the way I read this problem, and as far as I understand your code, that's my comment.
Note that L and R have the same parent only in the first call of this function. After that, L and R are not the left and right children of a single node like you would do in a traditional traversal. After the root node, L and R are the symmetrically corresponding nodes from the left subtree of the root and right subtree of the root. Please think about this. The tree doesn't have to be balanced for this code to work and for your example, it returns true.
The calls look like this for your example:
IsSymmetric(1)
IsSymmetric(2,3) // children of the root
IsSymmetric(4,5) // 2->left and 3->right
IsSymmetric(NULL,NULL) // 4->left and 5->right
IsSymmetric(NULL,NULL) // 4->right and 5->left
IsSymmetric(NULL,NULL) // 2->right and 3->left
As you can see, the end result is true since none of the calls to IsSymmetric(Node* L,Node* R) have one NULL and one non-NULL argument.
- crdmp January 12, 2012Let me show what my algorithm does with a simple example first. Let the initial array be [1,2,3,4,a,b,c,d]. Let's just say it's 1234abcd. In this example, n=4 according to the problem definition. I swap 3 pairs of elements in the middle around the center of the array as a block. And then, I swap 2 pairs of elements as a block, and finally I swap 1 pair of elements. It's hard to explain so I'll just show how it progresses:
initially: 1234abcd
swapping center 3 pairs, it becomes 1abc234d
swapping center 2 pairs, it becomes 1a23bc4d
swapping center 1 pair, it becomes 1a2b3c4d
It works in place but time complexity is O(n^2).
Here is the code. It's a little hard to understand but basically, it does what I explained above. I assumed an int array for sake of simplicity.
void swap(vector<int> & v, int i, int j) {
int t = v[i];
v[i] = v[j];
v[j] = t;
}
void process(vector<int> & v) {
int n = v.size()/2;
for ( int i = n-1; i > 0; i-- )
for ( int j = n-1; i+j>=n; j-- )
swap(v,j,i+j);
}
What do you mean by linked list is dynamic?
I guess I'm missing something very crucial. I was thinking of using a stack to keep the pointers of the linked list. No recursion, and I'm not manipulating the pointers in the list itself. Can you elaborate on the "dynamic"?
We need to check the left child of the left node, with the right child of the right node and vice versa. Complexity is O(n).
bool IsSymmetric(Node* r) {
if ( r == NULL ) return true;
return IsSymmetric(r->left, r->right);
}
bool IsSymmetric(Node* L, Node* R) {
if ( !L && !R ) return true;
if ( !L && R || L && !R ) return false;
return IsSymmetric(L->left, R->right) && IsSymmetric(L->right, R->left);
}
We can do this with a single depth first traversal and O(log(n)) space. Important thing is to traverse the right subtrees before the left subtrees. For each level of the tree, we keep a pointer to the last visited node in that level of the tree. In the helper function, we just set the rightChild of the current node to the corresponding element in the array and update the element in the array to be the current node so that next time we are visiting a node in that level, we set the rightChild of that node to the correct Node.
void populate(Node* n) {
vector<Node*> R;
populateHelper(n, R, 0);
}
void populateHelper(Node* n, vector<Node*> & R, int h) {
if ( n == NULL ) return; // obvious
// if we are at this level for the first time, initialize the
// corresponding element of R with NULL
if ( h == R.size() ) R.push_back(NULL);
n->rightChild = R[h]; // get last visited Node in that level from R
R[h++] = n; // update R and increment h
populateHelper(n->rightChild, R, h); // traverse right subtree first
populateHelper(n->leftChild, R, h);
}
I first find the difference in length of both linked lists and save this value in a variable called state. If state is positive, the first list is longer, if it's negative, the second list is longer and if it's 0, their lengths are equal.
To handle the carry properly, and to handle the difference in length, we need to do the addition starting from the end of the lists. So, I wrote a recursive function (Add2) that gets the then current head of the linked lists, a reference to int to pass the carry, and the value of the state variable. As long as the state variable is nonzero, we know that the two linked lists this function gets are not equal in length. That's why if the state variable is positive, we only add the value from the first linked list and if the state variable is negative, we only add the value from the second linked list.
The critical part happens here. Note that we only advance the pointer of the longer linked list while recursively calling Add2 at this point. The other important part is updating the state variable for the next call. We either increment or decrement the state value (whichever brings it closer to 0).
Only if they are equal in length, we add both of them and advance both pointers for the next call of Add2.
After we do the additions, we update the value of that node to be less than 10, and calculate the new carry. Since the carry variable is a reference, we can successfully pass this value to the previous call of our function. At the end, Add2 returns the head of the then current result. Inside Add, we also need to take care of the carry for cases where the result has more digits than both the first linked list and second linked list (e.g: 999+1). So if the carry is greater than 0, we create another node and put that node at the head of the resulting list.
Assuming only leaf nodes have values:
int UpdateTree(Node* n) {
if(n==NULL) return 0; // check if the pointer is NULL, this is needed
// if the root is NULL, or if a node has only 1
// child and we call this function on both
// children of that node. see below.
if(n->left || n->right) // if at least one child exists,
// update the value of the current node.
n->data = UpdateTree(n->left)+UpdateTree(n->right);
return n->data;
}
If internal nodes also have values that need to be summed with the subtrees, we don't need to check if at least one child exists. We can just add the values.
int UpdateTree(Node* n) {
if(n==NULL) return 0;
n->data += UpdateTree(n->left)+UpdateTree(n->right);
return n->data;
}
Following code is tested. It handles the case where first list is longer than the second, or second is longer than the first as well as when they are of equal length.
int FindLength(Node* n) { // find the length of a given linked list.
int ret = 0;
while(n) {
ret++;
n = n->next;
}
return ret;
}
Node* Add(Node* list1, Node* list2) { // this function is called first
int state = FindLength(list1) - FindLength(list2);
// if state > 0, list1 is longer
// if state < 0, list2 is longer
// if state == 0, list1 and list2 is of same length
int carry = 0;
Node* ret = Add2(list1, list2, carry, state); // add the two lists
if ( carry > 0 ) { // handle carry for the leftmost digit
Node* temp = new Node(carry);
temp->next = ret;
ret = temp;
}
return ret;
}
Node* Add2(Node* p1, Node* p2, int& carry, int state) { // helper function
if ( p1 == NULL && p2 == NULL ) // if both are NULL, we are at the end
return NULL;
Node* ret = new Node(0); // create new node to return
if ( state > 0 ) { // p1 is still longer than p2
// only advance p1's pointer and decrease state
ret->next = Add2(p1->next, p2, carry, state-1);
ret->data = carry + p1->data; // just sum carry and p1's data
}
else if ( state < 0 ) { // p2 is still longer than p1
// only advance p2's pointer and increase state
ret->next = Add2(p1, p2->next, carry, state+1);
ret->data = carry + p2->data; // just sum carry and p2's data.
}
else { // p1 and p2 are of same length
// advance both pointers, state should stay untouched from now on(0).
ret->next = Add2(p1->next, p2->next, carry, 0);
ret->data = carry + p1->data + p2->data; // sum carry and both digits
}
carry = ret->data / 10; // calculate new carry
ret->data %= 10; // update the current data to be smaller than 10
return ret; // return the new node
}
- crdmp December 26, 2011What about just recursively traversing the tree while giving a pointer to pointer to Node and a reference to the max value?
Node* maxSubtree(Node* r) {
int max = -oo;
Node* maxNode = NULL;
f(r, max, &maxNode);
return maxNode;
}
int f(Node* r, int& max, Node** maxNode) {
if(r==NULL) return 0;
int sum = f(r->left, max, maxNode) + f(r->right, max, maxNode) + r->data;
if(sum>max) {
max = sum;
*maxNode = r;
}
return sum;
}
If I understand your question, no. By definition of a tree, I think we need to include all the children (including leaves) of a given node if want to consider it as a tree.
- crdmp January 24, 2012