114.二叉树展开为链表

114. 二叉树展开为链表

给你二叉树的根结点 root ，请你将它展开为一个单链表：

• 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
• 展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例 1：

输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [0]
输出：[0]

提示：

• 树中结点数在范围 [0, 2000] 内
• -100 <= Node.val <= 100

进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？

C++

• 思路1:先序遍历二叉树,将每个节点放入 res , 然后遍历 res 改变树结构

/**
 * 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:
    vector<TreeNode*> res;
    void flatten(TreeNode* root) {
        if (!root) return;
        if(!root -> left && ! root -> right) return;
        preorder(root);
        for(int i = 1; i < res.size(); i++){
            root -> right = res[i];
            root -> left = nullptr;
            root = root ->right;
        }
    }

    void preorder(TreeNode* root){
        if(!root) return ;
        res.push_back(root);
        preorder(root -> left);
        preorder(root ->right);
    }
};

• 思路2 从后往前链接,先 4->5,再3->4->5, 2->3->4->5, 最后 1->2->3->4->5 本来先序顺序是 根->左->右 这里变成 右->左->根

TreeNode* last = nullptr;
void flatten(TreeNode* root) {
  if (root == nullptr) return;
  flatten(root->right);
  flatten(root->left);
  root->right = last;
  root->left = nullptr;
  last = root;
}

• 思路3:寻找前驱节点

前两种方法都借助前序遍历，前序遍历过程中需要使用栈存储节点。有没有空间复杂度是 O(1)的做法呢？

注意到前序遍历访问各节点的顺序是根、左、右。如果一个节点的左子节点为空，则该节点不需要进行展开操作。如果一个节点的左子节点不为空，则该节点的左子树中的最后一个节点被访问之后，该节点的右子节点被访问。该节点的左子树中最后一个被访问的节点是左子树中的最右边的节点，也是该节点的前驱节点。因此，问题转化成寻找当前节点的前驱节点

具体做法是，对于当前节点，如果其左子节点不为空，则在其左子树中找到最右边的节点，作为前驱节点，将当前节点的右子节点赋给前驱节点的右子节点，然后将当前节点的左子节点赋给当前节点的右子节点，并将当前节点的左子节点设为空。对当前节点处理结束后，继续处理链表中的下一个节点，直到所有节点都处理结束。

/**
 * 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:
    TreeNode* pre = nullptr;
    void flatten(TreeNode* root) {
        if(!root) return;
        if(root -> left){
            pre = root -> left;
            while(pre ->right){
                pre = pre ->right;
            }
            pre -> right = root ->right; 
            root -> right = root ->left;
        }
        root -> left =nullptr;
        flatten (root -> right); //把所有点都弄到root右边来了,所以只需向右走
    }
};