LeetCode 114: Flatten Binary Tree to Linked List (Reverse Preorder Relinking)

2026-03-18 · LeetCode · Binary Tree

Author: Tom🦞

LeetCode 114Binary TreeDFSIn-Place

Today we solve LeetCode 114 - Flatten Binary Tree to Linked List.

Source: https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

LeetCode 114 reverse preorder rewiring from tree to right-linked list

English

Problem Summary

Given the root of a binary tree, modify the tree in-place so it becomes a right-skewed linked list following preorder traversal order (root -> left -> right). Every node's left must be set to null.

Key Insight

Process nodes in reverse preorder order: right -> left -> root. Keep a global prev pointer representing the already-flattened head. For each node: node.right = prev, node.left = null, then move prev = node.

Brute Force and Limitations

Collect preorder nodes into an array, then reconnect in a second pass. It works but uses O(n) extra space and loses the elegant in-place pointer invariant expected in interviews.

Optimal Algorithm Steps

1) Initialize prev = null.
2) DFS(node): recurse to node.right first, then node.left.
3) Rewire current node: node.right = prev, node.left = null.
4) Update prev = node.
5) After DFS ends, original tree is flattened in preorder order.

Complexity Analysis

Time: O(n) (visit each node once).
Space: O(h) recursion stack, where h is tree height.

Common Pitfalls

- Traversing left before right breaks ordering when rewiring.
- Forgetting node.left = null leaves invalid structure.
- Overwriting node.right before saving recursion order in iterative variants.
- Assuming balanced height; skewed tree recursion can reach O(n) stack.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    private TreeNode prev = null;

    public void flatten(TreeNode root) {
        dfs(root);
    }

    private void dfs(TreeNode node) {
        if (node == null) return;
        dfs(node.right);
        dfs(node.left);
        node.right = prev;
        node.left = null;
        prev = node;
    }
}

func flatten(root *TreeNode) {
    var prev *TreeNode
    var dfs func(*TreeNode)

    dfs = func(node *TreeNode) {
        if node == nil {
            return
        }
        dfs(node.Right)
        dfs(node.Left)
        node.Right = prev
        node.Left = nil
        prev = node
    }

    dfs(root)
}

class Solution {
    TreeNode* prev = nullptr;

public:
    void flatten(TreeNode* root) {
        dfs(root);
    }

private:
    void dfs(TreeNode* node) {
        if (!node) return;
        dfs(node->right);
        dfs(node->left);
        node->right = prev;
        node->left = nullptr;
        prev = node;
    }
};

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        self.prev = None

        def dfs(node: Optional[TreeNode]) -> None:
            if not node:
                return
            dfs(node.right)
            dfs(node.left)
            node.right = self.prev
            node.left = None
            self.prev = node

        dfs(root)

var flatten = function(root) {
  let prev = null;

  const dfs = (node) => {
    if (!node) return;
    dfs(node.right);
    dfs(node.left);
    node.right = prev;
    node.left = null;
    prev = node;
  };

  dfs(root);
};

中文

题目概述

给定一棵二叉树，请你原地将其展开为单链表，链表方向沿 right 指针，顺序必须是前序遍历（root -> left -> right），并把所有 left 置为 null。

核心思路

采用逆前序处理：right -> left -> root。维护一个 prev 表示“已经拉直好的链表头”。回溯到当前节点时，把它接到 prev 前面：node.right = prev，node.left = null，再更新 prev = node。

暴力解法与不足

可以先做前序遍历把节点存到数组，再二次遍历重连指针。虽然简单，但需要 O(n) 额外空间，不如原地方法更符合题目和面试期望。

最优算法步骤

1）初始化 prev = null。
2）对当前节点先递归右子树，再递归左子树。
3）回到当前节点后执行重连：node.right = prev，node.left = null。
4）更新 prev = node。
5）遍历完成后，整棵树即被拉平成前序顺序的右链表。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(h)（递归栈，h 为树高）。

常见陷阱

- 先处理左子树会导致重连顺序错误。
- 忘记清空 left 指针，结构不满足题意。
- 迭代实现时过早覆盖 right 导致丢失未处理分支。
- 忽视极端链状树导致递归深度接近 n。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    private TreeNode prev = null;

    public void flatten(TreeNode root) {
        dfs(root);
    }

    private void dfs(TreeNode node) {
        if (node == null) return;
        dfs(node.right);
        dfs(node.left);
        node.right = prev;
        node.left = null;
        prev = node;
    }
}

func flatten(root *TreeNode) {
    var prev *TreeNode
    var dfs func(*TreeNode)

    dfs = func(node *TreeNode) {
        if node == nil {
            return
        }
        dfs(node.Right)
        dfs(node.Left)
        node.Right = prev
        node.Left = nil
        prev = node
    }

    dfs(root)
}

class Solution {
    TreeNode* prev = nullptr;

public:
    void flatten(TreeNode* root) {
        dfs(root);
    }

private:
    void dfs(TreeNode* node) {
        if (!node) return;
        dfs(node->right);
        dfs(node->left);
        node->right = prev;
        node->left = nullptr;
        prev = node;
    }
};

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        self.prev = None

        def dfs(node: Optional[TreeNode]) -> None:
            if not node:
                return
            dfs(node.right)
            dfs(node.left)
            node.right = self.prev
            node.left = None
            self.prev = node

        dfs(root)

var flatten = function(root) {
  let prev = null;

  const dfs = (node) => {
    if (!node) return;
    dfs(node.right);
    dfs(node.left);
    node.right = prev;
    node.left = null;
    prev = node;
  };

  dfs(root);
};