/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @return TreeNode类 */ vector<int> v; void dfs(TreeNode* root) { if(!root) return; v.emplace_back(root->val); dfs(root->left); dfs(root->right); } TreeNode* flattenTree(TreeNode* root) { // write code here if(!root) return nullptr; dfs(root); reverse(v.begin(), v.end()); // 根据先序遍历 TreeNode* ans = new TreeNode(v.back()); v.pop_back(); queue<TreeNode* >q; q.push(ans); while(!v.empty()) { int len = q.size(); for(int i=0; !v.empty() && i<len; ++i) { TreeNode* t = q.front(); q.pop(); t->left = nullptr; t->right = new TreeNode(v.back()); v.pop_back(); q.push(t->right); } } return ans; } };