LeetCode46 - 二叉树展开为链表

📝 题目描述

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

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

示例：

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

💡 解题思路

方法一：先序遍历

最容易想到的方法，既然题目要求我们先序遍历，那么我们就使用迭代法进行先序遍历，一边遍历一边连接节点。

方法二：寻找前驱节点

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

注意到前序遍历访问各节点的顺序是 根节点、左子树、右子树。

如果一个 节点A 的左子节点为空，则该节点不需要进行展开操作；
如果一个 节点A 的左子节点不为空，则 A 的左子树中的最后一个 节点B 被访问之后，A 的右子节点 C 被访问。A 的左子树中最后一个被访问的节点 B 是左子树中的最右边的节点，也是 C 的前驱节点。因此，问题转化成寻找前驱节点。

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

参考分步链接：力扣题解。

🔧 代码实现

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) {
        if (!root) return;
        stack<TreeNode*> st;
        TreeNode* dummy = new TreeNode(-1);
        TreeNode* last = dummy;
        st.push(root);
        while(!st.empty()) {
            TreeNode* temp = st.top(); st.pop();
            last -> right = temp;
            last -> left = nullptr;
            last = temp;
            if (temp -> right) st.push(temp -> right);
            if (temp -> left) st.push(temp -> left);
        }
        delete dummy;
    }
};

2、寻找前驱节点

/**
 * 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* curr = root;
        while (curr) {
            if (curr -> left) {
                TreeNode* pre = curr -> left;
                while (pre -> right) {
                    pre = pre -> right;
                }
                pre -> right = curr -> right;
                curr -> right = curr -> left;
                curr -> left = nullptr;
            }
            curr = curr -> right;
        }
    }
};

📊 复杂度分析

1、先序遍历

时间复杂度： $O(n)$ ，其中 n 是二叉树的节点数。前序遍历的时间复杂度是 $O(n)$ ，前序遍历的同时对每个节点更新左右子节点的信息，更新子节点信息的时间复杂度是 $O(1)$ ，因此总时间复杂度是 $O(n)$ 。
空间复杂度： $O(n)$ ，其中 n 是二叉树的节点数。空间复杂度取决于栈的大小，栈内的元素个数不会超过 n。

2、寻找前驱节点

时间复杂度： $O(n)$ ，其中 n 是二叉树的节点数。展开为单链表的过程中，需要对每个节点访问一次，在寻找前驱节点的过程中，每个节点最多被额外访问一次。
空间复杂度： $O(1)$ 。

🎯 总结

核心思想：掌握先序遍历的前提条件下再掌握方法二。