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
click to show hints.
深入理解了指针和树的操作，那么这道题是十分简单的，但是没理解好，那么这道题是非常难的。
重要一点：遍历访问的时候，不能改变没有访问过的树节点的结构。
也因为这一点，所以这道题不能像普通先序遍历那样写程序。
仔细观察思考会发现两点特征：
1 修改后的树只有右子树，
2 访问过之后的节点是可以修改其结构的
那么我们可以使用逆先序遍历 - 因为先访问最右边的右子树，那么这个右子树不会在后面的访问中需要了，就可以改变其树形结构了。
想清楚这一点之后，这道题就变得非常简单了。
下面两个逆先序遍历的程序都十分简单：
1.
void flatten(TreeNode *root)
{
if (!root) return;
TreeNode *dummy = new TreeNode(-1);
flatten(root, dummy);
//root = dummy->right;可以不用这句
delete dummy;
}
void flatten(TreeNode *root, TreeNode *(&res))
{
if (!root) return;
flatten(root->right, res);
flatten(root->left,res);
root->right = res->right;
res->right = root;
root->left = nullptr;
}
2.
void flatten2(TreeNode *root)
{
if (!root) return;
flatten2(root->right);
flatten2(root->left);
if (root->left)
{
TreeNode *rMost = root->left;
while (rMost->right) rMost = rMost->right;
rMost->right = root->right;
root->right = root->left;
root->left = nullptr;
}
}