## Flatten Binary Tree to Linked List

Flatten a binary tree to a fake “linked list” in pre-order traversal.

Here we use the

rightpointer in TreeNode as thenextpointer in ListNode.Have you met this question in a real interview?

Yes

Example`1 \ 1 2 / \ \ 2 5 => 3 / \ \ \ 3 4 6 4 \ 5 \ 6`

NoteDon’t forget to mark the left child of each node to null. Or you will get Time Limit Exceeded or Memory Limit Exceeded.

ChallengeDo it in-place without any extra memory.

/** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ class Solution { public: /** * @param root: a TreeNode, the root of the binary tree * @return: nothing */ void flatten(TreeNode *root) { // write your code here root = DFS(root, nullptr); } TreeNode* DFS(TreeNode *root, TreeNode * tail){ if(root == nullptr) return tail; TreeNode * right = DFS(root->right, tail); TreeNode * left = DFS(root->left, right); root->right = left; root->left = nullptr; return root; } };

Flatten binary tree, not a preorder approach. Functional correct but not an AC solution.

/** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ class Solution { public: /** * @param root: a TreeNode, the root of the binary tree * @return: nothing */ void flatten(TreeNode *root) { // write your code here if(root == nullptr) return ; TreeNode * tail, * head; head = tail = root; // move tail to right most node while(tail->right){ tail = tail->right; } while(head){ if(head->left){ tail->right = head->left; head->left = nullptr; while(tail->right){ tail = tail->right; } } head = head->right; } } };