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 ≤ N o d e . v a l ≤ 100 -100 \le Node.val \le 100 −100≤Node.val≤100

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

---

题解：

法一：

因为链表是先序遍历结果，优先考虑先序遍历。

如果使用递归的话，那么在将左子树接到根节点右子树过程中，会丢失了原来右子树的信息，因此，递归先序遍历不太现实。

考虑先序遍历迭代方式，有两种迭代方式实现：

第一种：

void preOrderStack( TreeNode* root ) {
    if ( !root ) return;
    stack<TreeNode*> stk;
    while ( stk.size() || root ) {
        while ( root ) {
            stk.push( root );
            root = root->left;
        }
        root = stk.top();
        stk.pop();
        root = root->right;
    }
}

第二种：

void preOrderStack( TreeNode* root ) {
    if ( !root ) return;
    stack<TreeNode*> stk;
    stk.push( root );
    whike ( stk.size() ) {
        root = stk.top();
        stk.pop();
        if ( root->right ) stk.push( root->right );
        if ( root->left ) stk.push( root->left );
    }
}

可以看到，在第一种迭代实现方式中，如果我们修改了根节点右指针指向，还是丢失右子树节点。而第二种方式提前将右子树节点保存在栈中，可以防止丢失。所以，我们可以利用第二种方式来通过先序遍历建立链表。

时间复杂度： O ( n ) O(n) O(n)

额外空间复杂度： O ( n ) O(n) O(n)

/**
 * 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:
    void flatten(TreeNode* root) {
        if ( !root ) return;
        vector<TreeNode*> stk;
        stk.emplace_back( root );
        TreeNode *pre = nullptr;
        while ( stk.size() ) {
            root = stk.back();
            stk.pop_back();
            if ( pre ) {
                pre->right = root;
                pre->left = nullptr;
            }
            if ( root->right ) stk.emplace_back( root->right );
            if ( root->left ) stk.emplace_back( root->left );
            pre = root;
        }
    }
};
/*
时间：4ms，击败：96.69%
内存：12.3MB，击败：88.68%
*/

法二：

先序遍历：根节点 左子树 右子树

逆后序遍历：右子树 左子树 根节点

两者是逆序的关系，于是我们可以考虑 逆后序 遍历，每遍历到一个节点就将当前节点的右指针更新为上一个节点。

时间复杂度： O ( n ) O(n) O(n)

额外空间复杂度： O ( n ) O(n) O(n)

/**
 * 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:
    void reversePostOrder( TreeNode* root, TreeNode*& pre) {
        if ( !root ) return;
        reversePostOrder( root->right, pre );
        reversePostOrder( root->left, pre );
        root->right = pre;
        root->left = nullptr;
        pre = root;
    }
    void flatten(TreeNode* root) {
        TreeNode *pre = nullptr;
        reversePostOrder( root, pre );
    }
};
/*
时间：4ms，击败：96.69%
内存：12.4MB，击败：77.11%
*/

也可以迭代实现，下面是后序遍历的迭代版本：

void postOrderStack(TreeNode* root) {
    stack<TreeNode*> stk;
    TreeNode *cur = root, *pre = nullptr;
    while ( cur || stk.size() ) {
        while ( cur ) {
            stk.push( cur );
            cur = cur->left;
        }
        cur = stk.top();
        if ( !cur->right || cur->right == pre ) {
            stk.pop();
            cout << cur->val << ' ';
            pre = cur;
            cur = nullptr;
        } else cur = cur->right;
    }
}

在上面修改一下即可：

/**
 * 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:
    void flatten(TreeNode* root) {
        TreeNode *pre = nullptr;
        stack<TreeNode*> stk;
        while ( root || stk.size() ) {
            while ( root ) {
                stk.push( root );
                root = root->right;
            }
            root = stk.top();
            if ( !root->left || root->left == pre ) {
                stk.pop();
                root->right = pre;
                root->left = nullptr;
                pre = root;
                root = nullptr;
            } else root = root->left;
        }
    }
};
/*
时间：4ms，击败：96.69%
内存：12.5MB，击败：76.24%
*/

法三：

考虑一种迭代方法：

• 将左子树插入到右子树的位置
• 将右子树接在左子树最右边的节点
• 考虑新的右子树根节点，重复上述过程，直到右子树为空

时间复杂度： O ( n ) O(n) O(n)

额外空间复杂度： O ( 1 ) O(1) 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:
    void flatten(TreeNode* root) {
        TreeNode *mostright = nullptr;
        while ( root ) {
            if ( root->left ) {
                mostright = root->left;
                while ( mostright->right ) mostright = mostright->right;
                mostright->right = root->right;
                root->right = root->left;
                root->left = nullptr;
            }
            root = root->right;
        }
    }
};
/*
时间：4ms，击败：96.96%
内存：12.3MB，击败：94.72%
*/