1.题目
2.思路
不能使用先序遍历（根-左-右），因为顺序应该是 上-下-上 的2个过程（下探和回溯），所以使用后序遍历。
递归的注意事项：不管函数内部细节如何处理，而是要看函数的作用、输入和输出。
递归flatten函数作用：将一个二叉树原地展开为链表
函数的输入：树的根结点
函数的输出：无
后序遍历，在“做事情”的步骤中，分为三步：
（1）将根结点的左子树变为链表
（2）将根结点的右子树变成链表
（3）将变成链表的右子树放在链表的左子树的最右边。
盗用leetcode“明知山有虎”用户的图：
3.代码
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: void flatten(TreeNode* root) { if(root==NULL){ return; } //将根结点的左子树变成链表 flatten(root->left); //将根结点的右子树变成链表 flatten(root->right); TreeNode* temp=root->right; //把树的右边换成左边的链表 root->right=root->left; //记得左边要置空 root->left=NULL; //找到树的最右边的结点 while(root->right!=NULL){ root=root->right; } //把右边的链表接到刚才树的最右边的结点 root->right=temp; } };
