【面试经典 150 | 二叉树】二叉树展开为链表

文章目录

写在前面
Tag
题目来源
解题思路
- 方法一：前序遍历
- 方法二：同步进行
- 方法三：原地操作
写在最后

写在前面

本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……

专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：

Tag：介绍本题牵涉到的知识点、数据结构；
题目来源：贴上题目的链接，方便大家查找题目并完成练习；
题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；
解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；
知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【二叉树】【前序遍历】【原地操作】

题目来源

114. 二叉树展开为链表

解题思路

方法一：前序遍历

一个朴素的解法是对二叉树进行前序遍历并记录节点到节点数组中，然后将节点数组中的每个节点的左子节点指向空节点，右子节点指向指向下一个节点。

代码

/**
 * 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) {
        vector<TreeNode*> tmp;
        preorder(root, tmp);
        int n = tmp.size();
        for(int i = 1; i < n; ++i) {
            TreeNode *pre = tmp.at(i-1), *curr = tmp.at(i);
            pre->left = nullptr;
            pre->right = curr;
        }
    }

    void preorder(TreeNode* root, vector<TreeNode*>& tmp) {
        if(root == nullptr) {
            return;
        }
        tmp.push_back(root);
        preorder(root->left, tmp);
        preorder(root->right, tmp);
    }
};

复杂度分析

时间复杂度： $O (n)$ ， $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;
        }
        stack<TreeNode*> stk;
        stk.push(root);
        TreeNode* prev = nullptr;
        while (!stk.empty()) {
            TreeNode* cur = stk.top(); stk.pop();
            if (prev) {
                prev->left = nullptr;
                prev->right = cur;
            }
            if (cur->right) {
                stk.push(cur->right);
            }
            if (cur->left) {
                stk.push(cur->left);
            }
            prev = cur;
        }
    }
};

复杂度分析

时间复杂度： $O (n)$ ， $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) {
        TreeNode* cur = root;
        while (cur) {
            if (cur->left) {
                TreeNode* next = cur->left;
                TreeNode* pre = next;
                while (pre->right) {
                    pre = pre->right;
                }
                pre->right = cur->right;
                cur->left = nullptr;
                cur->right = next;
            }
            cur = cur->right;
        }
    }
};

复杂度分析

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

空间复杂度： $O (1)$ 。