wordpress 帮助文档/seo关键词排名如何
题目：
114. 二叉树展开为链表
题解：
- 题解1：先序遍历，非原地算法，时间复杂度为O(n)，空间复杂度为O(n)
- 题解2：将右子树连接到左子树的最右边节点上，然后左子树移动到原来右子树的地方，最后将根节点的左子树赋为空
- 题解3：变形的后序遍历，遍历顺序为
右左根（已变形），主要要使用一个全局变量pre来保存已修改好的root节点。
题解1：
class Solution {
public://题解1：前序遍历将二叉树转换为链表，非原地算法void flatten(TreeNode* root){root=helper(root);} TreeNode* helper(TreeNode* root){if(root==nullptr)return root;TreeNode* head=new TreeNode(0);stack<TreeNode*> s;s.push(root);while(!s.empty()){TreeNode* top=s.top();s.pop();head->right=top;head->left=nullptr;//右子树先进栈，左子树后进栈，方便先访问左子树if(top->right!=nullptr)s.push(top->right);if(top->left!=nullptr)s.push(top->left);head=head->right;}return head->right;}
};
题解2：
class Solution {
public://题解2：将右子树连接到左子树的最右边节点上，然后左子树移动到原来右子树的地方，最后将根节点的左子树赋为空void flatten(TreeNode* root) {while(root!=nullptr){if(root->left==nullptr){//左子树为空，考虑下一个节点root=root->right;}else{TreeNode* pre=root->left;while(pre->right!=nullptr){//寻找左子树最右边的节点pre=pre->right;}pre->right=root->right;//右子树连接在左子树的最右边节点上root->right=root->left;//更新根节点的右子树root->left=nullptr;//左子树赋为空root=root->right;//考虑下一个节点}}}
};
题解3：
class Solution {
public://思路：变形的后序遍历，遍历顺序为右左根TreeNode* pre=nullptr;//pre的作用是保存已修改好的节点void flatten(TreeNode* root){if(root==nullptr)return;flatten(root->right);flatten(root->left);root->right=pre;root->left=nullptr;pre=root;}
};