Leetcode 114: flattern binary tree to link list //// convert binary tree to double link list

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

这个题目也属于serialize tree的问题， 把tree serialize 成single linklist。 对于把tree

serialize 成single linklist 或者 double linklist的算法是相似的， 基本思路： 都是运用一种tree 

traversal 的方法，当遍历到一个Node的时候， 对该node和previous node 进行指针的操作， 

需要对整个过程定义一个linklist的head指针， 然后需要有一个 pre指针，指向tree traversal

结果的previous的node，在当前层对current root 和 previous node指针进行操作。

当然对于不同的题目要求做法也有些不同。

这个题目观察发现，其实是对tree进行了pre-order traversal,所以可以用pre-order traversal

的过程来convert, 如果 pre = NULL，此时root -》head， 否则， pre-》right = root， pre->left = NULL

但是这样的话会有一个问题，在进行pre-》right=root的时候其实就改变了root-》right的值，所以

我们需要提前将root-》right的值保存在tmp里面，在对right subtree进行serialize的时候直接利用就可以

了。 

class Solution {
private:
    void helper(TreeNode* root, TreeNode* &head, TreeNode* &pre) {
        //base case
        if (root == NULL) return;
        TreeNode* tmp = root->right;
        if (pre == NULL) {
            head = root;
        } else {
            pre->right = root;
            pre->left = NULL;
        }
        pre = root;
        helper(root->left, head,pre);
        helper(tmp,head,pre);
    }
public:
//pre order
    void flatten(TreeNode* root) {
        TreeNode* head = NULL;
        TreeNode* pre = NULL;
        helper(root, head,pre);
        root = head;
        return;
    }
}; 

 time complexity: O(n)

space complexity: O(logn) //stack size

同样类似的题目有： convert binary tree to double linklist

这里采用preorder， inorder， postorder的顺序都可以，以inorder为例，

//simple recursion to convert the tree to double linked list

void SerializeTree(TreeNode* root, TreeNode* &head) {

    //base case

    if (root == NULL) return;

    //pre points to the previous node in inorder traversal ordering

    static TreeNode* pre = NULL;//staic here equals to global variable

    SerializeTree(root->left,head);

    if (pre == NULL) {

    head = root;

} else {

    pre->right = root;

    root->left = pre;

}

pre = root;

    SerializeTree(root->right,head);

}

 time complexity: O(n)

space complexity: O(logn)