【LeetCode热题100】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) 额外空间）展开这棵树吗？

四.解题思路

解法1：递归，每次让根指向左子树的最右结点，左子树最右结点指向根的右子树，空间复杂度 $o (1)$ 。
解法2：前序遍历，空间复杂度 $o (n)$

五.代码实现

优解

class Solution {
public:
    void flatten(TreeNode* root) {
        
        linkList(root);
    }

    TreeNode* linkList(TreeNode* root)
    {
    	//退出边界
       if(root == nullptr) return nullptr;
		
		
       TreeNode *left = linkList(root->left);
       TreeNode* right = linkList(root->right);
       //自底向上，默认左右子树都已按链表展开
       if(left) {
        TreeNode *leftTail = left;
        //获取当前root的左子树最右下结点
        while(leftTail->right) leftTail = leftTail->right;
        //根的右指针指向左子树
        root->right = left;
        //断开左指针
        root->left = nullptr;
        //左子树最右下结点指向右子树
        leftTail->right = right;
       }
       //返回给上一栈帧root
        return root;
    }

    
};

前序遍历

class Solution {
public:
    void flatten(TreeNode* root) {
        preorderTraversal(root);
        vector<TreeNode*>::iterator it;
        int size = pre.size();
        if(size == 0 || size == 1) return;
        for(it = pre.begin(); it < pre.begin() + size - 1; it++)
        {
            (*it)->left = nullptr;
            (*it)->right = *(it + 1);
        }
        if(*it != nullptr)
        {
            (*it)->left = nullptr;
            (*it)->right = nullptr;
        }
        
    }

    TreeNode* preorderTraversal(TreeNode* root) {
        if (root == nullptr) return nullptr;
        pre.push_back(root);
        preorderTraversal(root->left);
        preorderTraversal(root->right);
        return root;
    }

private:
    vector<TreeNode*> pre;
};