力扣hot100——114.二叉树展开为链表

基于 Morris 遍历思想

将左子树插到右子树的位置，将原来的右子树插到左子树的最右结点，遍历右结点重复以上步骤，直至右结点为空。

class Solution {
public:void flatten(TreeNode* root) {if(root==nullptr) return;while(root){if(!root->left) root=root->right;else{//找到左子树的最右结点TreeNode* node=root->left;while(node->right){node=node->right;}node->right=root->right;root->right=root->left;root->left=nullptr;//遍历root=root->right;}}}
};

• 时间复杂度：O（n）
• 空间复杂度：O（1）

后序遍历

链表的顺序与先序遍历相同，但如果在先序遍历中修改指针指向会丢失原本的右孩子，无法完全遍历。那么不妨进行后序遍历，此时会先遍历右左孩子，然后更改指针指向。

class Solution {
public:TreeNode* pre=nullptr;void flatten(TreeNode* root) {if(root==nullptr) return;flatten(root->right);//遍历右子树flatten(root->left);//遍历左子树root->right=pre;//更改指向root->left=nullptr;pre=root;//更新pre}
};

• 时间复杂度：O（n）
• 空间复杂度：O（h）h为树的高度，递归调用栈