leetcode leetcode 二叉树 递归

二叉树展开为单链表

LeetCode 114 题解笔记

Posted by BY on April 26, 2026
CATALOG

    原始笔记给了一句”函数式编程，只考虑函数以及结果”。这里把题意和递归的返回值含义补一下，代码保持原样。

    题目背景

    LeetCode 114「二叉树展开为链表」。要求把一棵二叉树原地展开为一条单链表：所有节点 left 置空，right 按先序遍历顺序依次链接。

    概念解释

    • 先序遍历（preorder）：根 → 左子树 → 右子树。
    • 原地修改：不能借助新数组/新节点，只能调整 left/right 指针。
    • 函数式递归思路：忽略函数内部如何把树拆开，只关心”调用 flatten_helper(t) 后会返回一棵已经按先序展开成右链的树”。

    实现原理

    flatten_helper(root) 的契约：把以 root 为根的子树就地展开，所有节点串到 right 链上，并返回新链表头（实际上仍是 root）。

    1. 暂存 root 的左右孩子 lhv、rhv，把 root->left 置空。
    2. 递归展开左子树，作为 root 的新右子树挂上去。
    3. 沿着 right 一直走到末端节点，那里就是”左子树展开后的尾节点”。
    4. 把 rhv 递归展开后接在尾节点的 right 上，整段链表头依然是最初的 root。

    直观对应了先序的拼接顺序：根 + 左子树展开结果 + 右子树展开结果。

    时间复杂度 O(n^2) 最坏（每层都要走到链尾），空间复杂度 O(h) 递归栈。Morris 解法可以做到 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 {
    private:
    TreeNode* flatten_helper(TreeNode* root)
    {
        if(root == nullptr)
        {
            return nullptr;
        }
        TreeNode* new_root = root;
        TreeNode* rhv = root->right;
        TreeNode* lhv = root->left;
        root->left = nullptr;
        root->right = flatten_helper(lhv);
        while(root->right != nullptr)
        {
            root = root->right;
        }

        root->right = flatten_helper(rhv);
        return new_root;
    }
public:
    void flatten(TreeNode* root) {
        root =  flatten_helper(root);
    }
};
    FEATURED TAGS
    Git Cheat Sheet Markdown Tools C++ Linker Thread Linux TCP Network GDB Debug leetcode 链表 WSL Ubuntu Windows Linux Kernel GCC Android adb Troubleshooting Profiling Sanitizer glibc MySQL Database Python curl Build ELF clang-format CMake Graphviz Performance vcpkg Protobuf 排查 速查 内存 STL 调试 性能分析 性能 读书笔记 方法论 架构 网络 Timer mbedTLS TLS 安全 负载均衡 脚本 工具 LRU 二叉树 BST 中序遍历 回溯 二分查找 优先队列 排序 旋转数组 jenkins 部署
    FRIENDS