刷题No9 LeetCode114. Flatten Binary Tree to Linked 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
题目解析：此题为改变二叉树的结构，与单纯的先序遍历还有很大的区别。
参考：http://www.cnblogs.com/grandyang/p/4293853.html
http://www.jiuzhang.com/solutions/flatten-binary-tree-to-linked-list/
版本一（从上往下递归）:

747807982639154479.jpg

//version1
TreeNode *LastNode=NULL;
    void flatten(TreeNode *root) {
        if(root==NULL)
            return;
        if(LastNode!=NULL){
            LastNode->left=NULL;
            LastNode->right=root;
        }
        LastNode=root;
        TreeNode *right=root->right;
        flatten(root->left);
        flatten(right);
    }

版本二（从下往上递归）：

2017-01-07_221304.png

void flatten(TreeNode *root) {
    if (root == NULL)
        return;
    flatten1(root->left);
    flatten1(root->right);
    TreeNode *node = root->right;
    root->right = root->left;
    root->left = NULL;
    while (root->right) root = root->right;
    root->right = node;
}

版本三（非递归）：
同先序遍历的非递归版本类似，加入了连接操作

void flatten(TreeNode *root) {
    if (root == NULL)
        return;
    stack<TreeNode *>stk;
    stk.push(root);
    TreeNode *node = root;
    while (!stk.empty()) {
        node = stk.top();
        stk.pop();
        if (node->right != NULL)
            stk.push(node->right);
        if (node->left != NULL)
            stk.push(node->left);
        node->left = NULL;
        if (!stk.empty())
            node->right = stk.top();
        else
            node->right = NULL;
    }
}

版本四（非递归）：从根节点开始，将根节点的左子树插到根节点与右子树中间。

void flatten(TreeNode *root) {
    if (root == NULL)
        return;
    while (root) {
        if (root->left) {
            TreeNode *pre = root->left;
            while (pre->right)
                pre = pre->right;
            pre->right = root->right;
            root->right = root->left;
            root->left = NULL;
        }
        root = root->right;
    }
}