思路分析
题意是将二叉树按照指定的规则转换为单向链表，但是这题就有些难度了。树的问题基本都要利用其递归性质，这题的难点就在于，程序中的递归结构是非对称的。仔细观察转换规则，我们会发现转换后的链表对应的就是二叉树先序遍历的结果。这样的话，我们定义DFS函数的功能为：将某个子树转换为单向链表，并返回其起始节点的指针。
此时我们的分治策略就是，首先递归地将左右子树转化为单向链表，然后根节点连接到左子树，接下来从根节点顺着走到链表终点，再连接到右子树所转化成的链表上面去，即可完成整个转换过程。递归的代码实现出来非常简洁，但需要注意的一点是，由于题目中使用right指针代替链表的next指针，因此转换时要把所有left指针统一设置为NULL，否则会报RE错误。
代码
class Solution {
public:
void flatten(TreeNode *root) {
DFS(root);
}
TreeNode *DFS(TreeNode *root) {
if ( root == NULL ) return NULL;
TreeNode *pRight = DFS(root->right);
root->right = DFS(root->left);
root->left = NULL;
TreeNode *p = root;
while ( NULL != p->right ) p = p->right;
p->right = pRight;
return root;
}
};