114. Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.
For example, given the following tree:
1 / \ 2 5 / \ \ 3 4 6
The flattened tree should look like:
1
\
2
\
3
\
4
\
5
\
6
把一棵二叉树展开成一个链表，链表还是借助树的数据结构，只不过是借用了树的右孩子指针作为链表的指针。 仔细观察发现新的链表的顺序和树的先序遍历的顺序一致，如果能使用额外的空间，则先序遍历后把节点存到数组中，然后依次链接起来。 如果不使用额外空间，则只能想办法在DFS时就建立好链接关系。先序遍历的顺序是根左右，但是这题为了方便，我们先对右孩子建立链表，然后把右孩子接到父亲的左孩子的最右下角的节点上。比如上图中，我们建立好5->6的链表之后，需要把它接到4号节点的右边。
1
/
2
/ \
3 4
\
5
\
6
所以针对右孩子，我们需要根据父节点找到父节点的左子树的最右下角的节点。但是针对左孩子时，因为此时右孩子已经建立好链表并且接到了左孩子正确的位置上，所以只需要把左孩子接到父亲的右孩子位置，并把原来的左孩子置空，下图就是把上图1的左子树放到了右边，左边置为空。
1
\
2
/ \
3 4
\
5
\
6
完整代码如下：
class Solution2 {
public:
void dfs(TreeNode* par, TreeNode* cur)
{
if (cur == NULL)
return;
if (par) {
if (cur == par->right) {
if (par->left) {
TreeNode* tmp = par->left;
while (tmp->right)
tmp = tmp->right;
tmp->right = cur;
par->right = NULL;
}
}
else {
par->right = cur;
par->left = NULL;
}
}
if (cur->right)
dfs(cur, cur->right);
if (cur->left)
dfs(cur, cur->left);
}
void flatten(TreeNode* root) { dfs(NULL, root); }
};本代码提交AC，用时6MS。
还有一种思路比这简单，上面的解法需要while循环查找左兄弟的最右下角的节点，如果我们在DFS中直接返回尾节点，就不需要while查找了。
假设某节点的左右子树T(root->left)和T(root->right)已经flatten成linked list了：
1
/ \
2 5
\ \
3 6 <- rightTail
\
4 <- leftTail
如何将root、T(root->left)、T(root->right) flatten成一整个linked list？显而易见：
leftTail->right = root->right;
root->right = root->left;
root->left = NULL;
这里需要用到已经flatten的linked list的尾部元素leftTail, rightTail。所以递归返回值应该是生成的整个linked list的尾部。
代码如下：
class Solution {
public:
TreeNode* dfs(TreeNode* root)
{
if (!root)
return NULL;
TreeNode* leftTail = dfs(root->left);
TreeNode* rightTail = dfs(root->right);
if (root->left) {
leftTail->right = root->right;
root->right = root->left;
root->left = NULL;
}
if (rightTail)
return rightTail;
if (leftTail)
return leftTail;
return root;
}
void flatten(TreeNode* root) { dfs(root); }
};本代码提交AC，用时6MS。
完整代码如下：
[cpp]
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if (root == NULL)return "";
string ans = to_string(root->val);
if (root->left) ans += ","+serialize(root->left);
if (root->right) ans += ","+serialize(root->right);
return ans;
}
void insert(TreeNode* root, TreeNode* node) {
if (node->val < root->val) {
if (root->left == NULL)root->left = node;
else insert(root->left, node);
}
else {
if (root->right == NULL)root->right = node;
else insert(root->right, node);
}
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
if (data == "")return NULL;
TreeNode* root = NULL;
for (int start = 0, end = 0; end <= data.size(); ++end) {
if (data[end] == ‘,’ || end == data.size()) {
TreeNode* node = new TreeNode(atoi(data.substr(start, end – start).c_str()));
if (root == NULL)root = node;
else insert(root, node);
start = end + 1;
}
}
return root;
}
};
[/cpp]
本代码提交AC，用时26MS。]]>
