PU Flatten Binary Tree to Linked List

         1
        / 
       2   5
      /    
     3   4   6

   1
    
     2
      
       3
        
         4
          
           5
            
             6

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
void flatten(struct TreeNode* root) {
    while (root && !root->left) root = root->right;
    if (!root) return;
    struct TreeNode *p = root->left;
    while (p->right) p = p->right;
    p->right = root->right;
    root->right = root->left;
    root->left = 0;
    flatten(root->right);
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode *preorder(struct TreeNode *root, struct TreeNode *tail) {
    if (!root) return tail;
    tail->left = 0;
    tail->right = root;
    struct TreeNode *right = root->right;
    tail = preorder(root->left, root);
    return preorder(right, tail);
}
void flatten(struct TreeNode* root) {
    if (!root) return;
    struct TreeNode dummy;
    preorder(root, &dummy);
}