迭代法一：额外容器，前序遍历暴力求解（空间O(n))

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:void flatten(TreeNode* root) {stack<TreeNode*> stk;vector<TreeNode*> v;TreeNode* tmp = nullptr;TreeNode* cur = root;while(cur || stk.size()){while(cur){v.push_back(cur);stk.push(cur->right);cur = cur->left;}cur = stk.top();stk.pop();}for(int i = 1; i < v.size(); i++){   tmp = v[i-1];cur = v[i];tmp->left = nullptr;tmp->right = cur;}}
};

迭代法二： 嫁接法，不使用额外容器（空间O(1))

算法思路：

按照题目给的例子来说

1. 先把1-5这个链子断掉，存储一下5-6

2. 然后把1-2断掉，以2为头结点的存储到1的右节点去，找到以2为头结点的最右结点，把5接在后面。

3. 然后继续重复这样的操作。

文字说不清楚，可以看下参考图：

class Solution {
public:void flatten(TreeNode* root) {//if(!root)return;TreeNode* p = root;while(p){if(p->left){TreeNode* t = p->right;p->right = p->left;p->left = nullptr;TreeNode* q = p;while(q->right){if(q->right) q = q->right;}q->right = t;}p = p->right;}}
};