Problem Statment
https://binarysearch.com/problems/Binary-Tree-to-Linked-List/
Intuition
By Traversing InOrder(Left-Node-Right), We can create the linkedlist.
Implementation
Here we are taking a global variable prev and creating a new node while inorder traversing and pointing to the next of previous node. prev->next = new LLNode(root->val);
Here in main function, we created a dummy variable to store the head of the linkedlist.
Time Complexity
O(n) : For In-order traversing
Space Complexity
O(n) : For creating Linklist node
Code
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
/** * class Tree { * public: * int val; * Tree *left; * Tree *right; * }; */ /** * class LLNode { * public: * int val; * LLNode *next; * }; */ void helper(Tree* root, LLNode*& prev) { if (!root) return; helper(root->left, prev); prev->next = new LLNode(root->val); prev = prev->next; helper(root->right, prev); } LLNode* solve(Tree* root) { LLNode *dummy = new LLNode(-1, NULL), *prev = dummy; helper(root, prev); return dummy->next; } |
Recent Comments