给定一个二叉树，原地将它展开为一个单链表。
例如，给定二叉树
1
/ \
2 5
/ \ \
3 4 6
将其展开为：
1
\
2
\
3
\
4
\
5
\
6
class Solution {
public:
void flatten(TreeNode* root) {
preoder(root);
}
TreeNode* preoder(TreeNode* root){ // 借助前序遍历完成树的展开
if (root == nullptr) return nullptr;
TreeNode* back = root->right; // 备份右子树
TreeNode* backRoot = root; // 备份根节点
root->right = preoder(root->left);
root->left = nullptr; // 左子树置空
while(root->right) root = root->right;// 走到左子树展开链表的最后一个非空结点上
root->right = preoder(back); // 将右子树的展开链表接在原有链表的后面
return backRoot; // 返回根节点
}
};
