LeetCode - Flatten Binary Tree to Linked List | Darren's Blog

Given a binary tree, flatten it to a linked list in-place.

For example,given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.
Recursive Version: 
From http://fisherlei.blogspot.com/2012/12/leetcode-flatten-binary-tree-to-linked.html
void flatten(TreeNode *root) {  
       // Start typing your C/C++ solution below  
       // DO NOT write int main() function  
       if(root == NULL)  
            return;  
       ConvertToLink(root);  
  }  
  TreeNode* ConvertToLink(TreeNode* node)  
  {  
       if(node->left == NULL && node->right == NULL)  
            return node;  
       TreeNode* rHead = NULL;  
       if(node->right != NULL)  
           rHead = ConvertToLink(node->right);               
       TreeNode* p = node;  
       if(node->left!=NULL)  
       {  
            TreeNode* lHead = ConvertToLink(node->left);   
            node->right = lHead;  
            lHead->left = NULL;  
            node->left = NULL;  
            while(p->right!=NULL)  
                 p = p->right;  
       }       
       if(rHead != NULL)  
       {  
            p->right = rHead;  
            rHead->left = NULL;  
       }  
       return node;  

  }
[已犯错误]
1. Line 13~14
    刚开始的时候，首先flatten左树，然后处理右树。但是这样会导致处理右树的时候，节点的值已经在处理树的时候被破坏了。比如树为{1,2,3}，
     1
  /     \
2       3
如果先处理左树的话，当执行node->right = lhead的时候，右节点就已经被破坏了，node->right指向了2，而不是3。
1
   \
     2  (3)
当然，也可以用一个变量在处理左树前，保存右树地址。但是没必要，先处理右树就好了。
2. Line 22~23
    该循环是用于将p指针遍历到左树链表的最右节点。第一版时，这个循环是放在if语句以外，这就导致了，不必要的迭代了。比如当输入为{1,#,2}时，这个while循环会导致p指针遍历到右子树的最右节点，这显然是错的。
3. Line 20, 28
    不要忘了清空每一个指针，在新的链表中，左指针没必要保留
from http://www.darrensunny.me/leetcode-flatten-binary-tree-to-linked-list/

private TreeNode recursiveFlatten(TreeNode t) {

        if (t == null)      // Empty tree

            return null;

        // Recursively flatten its left and right subtrees

        TreeNode leftLeaf = recursiveFlatten(t.left);

        TreeNode rightLeaf = recursiveFlatten(t.right);

        if (leftLeaf == null && rightLeaf == null)    // The tree is a leaf itself

            return t;

        if (leftLeaf == null)    // Has only right subtree; already flattened

            return rightLeaf;

        if (rightLeaf == null) { // Has only left subtree; make it right

            t.right = t.left;

            t.left = null;

            return leftLeaf;

        }

        // Has both left and right subtrees

        // Put the left subtree in between the root and the right subtree

        TreeNode temp = t.right;

        t.right = t.left;

        t.left = null;

        leftLeaf.right = temp;

        return rightLeaf;

    }

Iterative Version: Use stack from http://www.programcreek.com/2013/01/leetcode-flatten-binary-tree-to-linked-list/
Go down through the left, when right is not null, push right to stack.

public void flatten(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode p = root;
 
        while(p != null || !stack.empty()){
 
            if(p.right != null){
                stack.push(p.right);
            }
 
            if(p.left != null){
                p.right = p.left;
                p.left = null;
            }else if(!stack.empty()){
                TreeNode temp = stack.pop();
                p.right=temp;
            }
 
            p = p.right;
        }
    }

Also read http://blog.csdn.net/perfect8886/article/details/20000083
Read full article from LeetCode - Flatten Binary Tree to Linked List | Darren's Blog