题目：

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

代码：

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    void flatten(TreeNode* root) {            if (!root) return;            stack
     
       sta;            TreeNode *dummy = new TreeNode(INT_MIN);            TreeNode *pre = dummy;            dummy->right = root;            sta.push(root);            while ( !sta.empty() )            {                TreeNode *tmp = sta.top(); sta.pop();                if ( tmp->right ) sta.push(tmp->right);                if ( tmp->left ) sta.push(tmp->left);                tmp->left = NULL;                pre->right = tmp;                pre = tmp;            }    }};
     

tips：

先序遍历（node->left->right）；每次出栈的元素都切断left（为什么right不用切？因为在下一次迭代的时候，pre->right自然就把right的值覆盖了）。

设立一个pre节点，保存上一次出栈的元素。

pre->right = tmp就能按照题意把原有的tree给flatten了。

===================================

学习了一个递归版的代码

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    void flatten(TreeNode* root) {        // terminal condition        if (!root) return;        // recersive left and child        flatten(root->left);        flatten(root->right);        // if left is not null then do the reconnection        if (!root->left) return;        TreeNode *p = root->left;        while ( p->right) p = p->right;        p->right = root->right;        root->right = root->left;        root->left = NULL;    }};

===================================================

第二次过这道题，使用非递归版做的，一开始忘记了给left方向断开，改了一次之后AC了。

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    void flatten(TreeNode* root) {            stack
     
       sta;            TreeNode* pre = new TreeNode(0);            if ( root ) sta.push(root);            while ( !sta.empty() )            {                TreeNode* tmp = sta.top();                sta.pop();                pre->right = tmp;                pre->left = NULL;                if ( tmp->right ) sta.push(tmp->right);                if ( tmp->left ) sta.push(tmp->left);                pre = tmp;            }    }};