// output list Node *list = NULL; void convert_to_doubly_ll(Node *root) { if (root == NULL) return; convert_to_doubly_ll(root->left); if (list) { list->right = root; root->left = list; } list = root; Node *right = root->right; root->right = NULL; convert_to_doubly_ll(right); }
If you want to do this in place, then all you have to do is pass in the previous node in each recursive call. The code is given below:
void convert_to_doubly_ll_in_place(Node *root, Node **prev) { if (root == NULL) return; convert_to_doubly_ll_in_place(root->left, prev); Node *prev_node = *prev; Node *right = NULL; if (prev_node) { prev_node->right = root; root->left = prev_node; } *prev = root; right = root->right; root->right = NULL; convert_to_doubly_ll_in_place(right, prev); }
You can call the above method like this:
Node *root = ....a tree...; Node *prev=NULL; convert_to_doubly_ll_in_place(root, &prev);
No comments:
Post a Comment