基于 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為樹的高度，遞歸調用棧