题目：Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.
For example,
Given1 / \ 2 5 / \ \ 3 4 6
The flattened tree should look like:
1 \ 2 \ 3 \ 4 \ 5 \ 6
Hints: 
View Code View Code
If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.
个人思路：
1、创建一个队列，把节点按照先序遍历的顺序入队
2、把节点挨个出队，前一个出队节点是后一个出队节点的父节点，后一个出队节点是前一个出队节点的右孩子节点，且每个非叶节点的左孩子为空
代码：
1 #include2 #include 3 #include 4 5 using namespace std; 6 7 struct TreeNode 8 { 9 int val;10 TreeNode *left;11 TreeNode *right;12 TreeNode(int x) : val(x), left(NULL), right(NULL) {}13 };14 15 class Solution16 {17 public:18 void flatten(TreeNode *root)19 {20 if (!root)21 {22 return;23 }24 25 queue preNodes;26 preorder(root, preNodes);27 root = preNodes.front();28 preNodes.pop();29 TreeNode * currentNode = root;30 while (!preNodes.empty())31 {32 TreeNode *tmp = preNodes.front();33 preNodes.pop();34 currentNode->right = tmp;35 currentNode->left = NULL;36 currentNode = currentNode->right;37 }38 }39 private:40 void preorder(TreeNode *root, queue &preNodes)41 {42 if (!root)43 {44 return;45 }46 preNodes.push(root);47 preorder(root->left, preNodes);48 preorder(root->right, preNodes);49 }50 };
在网上看到一个比较普遍的递归算法，链接：，里面有比较详细的思路解析，可以参考，大致思路是这样：要扁平化一棵树，则扁平化根节点的左子树和右子树，然后将左子树放到根节点的右孩子位置，右子树放到左子树的叶节点的右孩子位置
代码：
1 #include2 #include 3 #include 4 5 using namespace std; 6 7 struct TreeNode 8 { 9 int val;10 TreeNode *left;11 TreeNode *right;12 TreeNode(int x) : val(x), left(NULL), right(NULL) {}13 };14 15 class Solution16 {17 public:18 void flatten(TreeNode *root)19 {20 /*21 if (!root)22 {23 return;24 }25 26 queue preNodes;27 preorder(root, preNodes);28 root = preNodes.front();29 preNodes.pop();30 TreeNode * currentNode = root;31 while (!preNodes.empty())32 {33 TreeNode *tmp = preNodes.front();34 preNodes.pop();35 currentNode->right = tmp;36 currentNode->left = NULL;37 currentNode = currentNode->right;38 }39 */40 41 if (!root)42 {43 return;44 }45 if (root->left)46 {47 flatten(root->left);48 }49 if (root->right)50 {51 flatten(root->right);52 }53 if (!root->left)54 {55 return;56 }57 58 TreeNode *left_leaf = root->left;59 while (left_leaf->right)60 {61 left_leaf = left_leaf->right;62 }63 left_leaf->right = root->right;64 root->right = root->left;65 root->left = NULL;66 }67 private:68 void preorder(TreeNode *root, queue &preNodes)69 {70 if (!root)71 {72 return;73 }74 preNodes.push(root);75 preorder(root->left, preNodes);76 preorder(root->right, preNodes);77 }78 };
链接中还有一个非递归的思路，大家也可以看看