Flatten Binary Tree to Linked List

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

Here we use the right pointer in TreeNode as the nextpointer 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

Note

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

Challenge

Do 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;
        }
    }
};