快捷導(dǎo)航

Java實(shí)現(xiàn)將二叉樹(shù)展開(kāi)為鏈表的兩種方法

更新時(shí)間：2025年05月08日 10:06:16 作者：進(jìn)擊的小白菜

文章介紹了兩種方法將二叉樹(shù)按前序遍歷順序展開(kāi)為單鏈表,方法一為迭代法,方法二為前序遍歷+列表重建,兩者各有優(yōu)缺點(diǎn),選擇時(shí)需根據(jù)實(shí)際需求和場(chǎng)景考慮,下面小編給大家詳細(xì)說(shuō)說(shuō)

問(wèn)題描述

給定一棵二叉樹(shù)的根節(jié)點(diǎn) `root``，要求將其按前序遍歷的順序展開(kāi)為一個(gè)單鏈表。展開(kāi)后的鏈表應(yīng)滿足以下條件：

鏈表的順序與二叉樹(shù)的前序遍歷結(jié)果一致。
鏈表中每個(gè)節(jié)點(diǎn)的右子指針指向下一個(gè)節(jié)點(diǎn)，左子指針始終為 null。

示例輸入與輸出

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

輸出：[1,null,2,null,3,null,4,null,5,null,6]

解決方案

方法一：迭代法（Morris遍歷思路）

核心思想：通過(guò)修改指針實(shí)現(xiàn)原地展開(kāi)，無(wú)需額外空間。類似Morris遍歷，時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)。

實(shí)現(xiàn)步驟

初始化當(dāng)前節(jié)點(diǎn)：從根節(jié)點(diǎn)開(kāi)始遍歷。
處理左子樹(shù)：對(duì)于每個(gè)節(jié)點(diǎn)，若存在左子樹(shù)，找到左子樹(shù)的最右節(jié)點(diǎn)。
調(diào)整指針：
- 將左子樹(shù)的最右節(jié)點(diǎn)的右指針指向當(dāng)前節(jié)點(diǎn)的右子樹(shù)。
- 將當(dāng)前節(jié)點(diǎn)的右指針指向左子樹(shù)，左指針置空。
迭代處理：沿右指針處理下一個(gè)節(jié)點(diǎn)，直到所有節(jié)點(diǎn)處理完畢。

Java代碼實(shí)現(xiàn)

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public void flatten(TreeNode root) {
        TreeNode curr = root;
        while (curr != null) {
            if (curr.left != null) {
                // 找到左子樹(shù)的最右節(jié)點(diǎn)
                TreeNode prev = curr.left;
                while (prev.right != null) {
                    prev = prev.right;
                }
                // 將右子樹(shù)接到最右節(jié)點(diǎn)
                prev.right = curr.right;
                // 將左子樹(shù)移到右側(cè)，并清空左側(cè)
                curr.right = curr.left;
                curr.left = null;
            }
            // 處理下一個(gè)節(jié)點(diǎn)
            curr = curr.right;
        }
    }
}

關(guān)鍵解釋

左子樹(shù)的最右節(jié)點(diǎn)：前序遍歷中，左子樹(shù)的最后一個(gè)節(jié)點(diǎn)需要連接到當(dāng)前節(jié)點(diǎn)的右子樹(shù)。
指針調(diào)整：通過(guò)修改指針實(shí)現(xiàn)原地展開(kāi)，無(wú)需額外空間。

方法二：前序遍歷+列表重建

核心思想：顯式存儲(chǔ)前序遍歷結(jié)果，再重建鏈表。時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(n)。

實(shí)現(xiàn)步驟

前序遍歷存儲(chǔ)節(jié)點(diǎn)：遞歸遍歷二叉樹(shù)，按前序順序?qū)⒐?jié)點(diǎn)存入列表。
重建鏈表：遍歷列表，將每個(gè)節(jié)點(diǎn)的左指針置空，右指針指向下一個(gè)節(jié)點(diǎn)。

Java代碼實(shí)現(xiàn)

import java.util.ArrayList;
import java.util.List;

class Solution {
    public void flatten(TreeNode root) {
        if (root == null || (root.left == null && root.right == null)) return;
        List<TreeNode> result = new ArrayList<>();
        preOrder(root, result);
        // 重建鏈表
        for (int i = 0; i < result.size() - 1; i++) {
            TreeNode prev = result.get(i);
            TreeNode cur = result.get(i + 1);
            prev.left = null;
            prev.right = cur;
        }
    }

    private void preOrder(TreeNode root, List<TreeNode> result) {
        if (root == null) return;
        result.add(root);
        preOrder(root.left, result);
        preOrder(root.right, result);
    }
}

關(guān)鍵解釋

前序遍歷列表：顯式存儲(chǔ)節(jié)點(diǎn)順序，邏輯直觀。
空間開(kāi)銷：需額外存儲(chǔ)所有節(jié)點(diǎn)的引用，空間復(fù)雜度為O(n)。

方法對(duì)比與分析

特性	方法一（迭代法）	方法二（前序遍歷+列表）
時(shí)間復(fù)雜度	O(n)	O(n)
空間復(fù)雜度	O(1)	O(n)
代碼復(fù)雜度	高（需處理指針調(diào)整）	低（邏輯直觀）
棧溢出風(fēng)險(xiǎn)	無(wú)	有（遞歸深度高時(shí)）
適用場(chǎng)景	內(nèi)存敏感、大規(guī)模數(shù)據(jù)	快速實(shí)現(xiàn)、小規(guī)模數(shù)據(jù)

選擇建議

優(yōu)先方法一：
- 適用場(chǎng)景：內(nèi)存受限（如嵌入式開(kāi)發(fā)）、處理超大規(guī)模樹(shù)。
- 優(yōu)點(diǎn)：原地修改，無(wú)額外空間開(kāi)銷。
- 缺點(diǎn)：指針操作復(fù)雜，需深入理解Morris遍歷。
優(yōu)先方法二：
- 適用場(chǎng)景：快速實(shí)現(xiàn)、代碼可讀性優(yōu)先、小規(guī)模數(shù)據(jù)。
- 優(yōu)點(diǎn)：邏輯清晰，易于調(diào)試。
- 缺點(diǎn)：空間開(kāi)銷大，遞歸可能棧溢出。

拓展：方法二的迭代優(yōu)化

將遞歸前序遍歷改為迭代實(shí)現(xiàn)，避免棧溢出風(fēng)險(xiǎn)：

private void preOrder(TreeNode root, List<TreeNode> result) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode node = root;
    while (node != null || !stack.isEmpty()) {
        while (node != null) {
            result.add(node);
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();
        node = node.right;
    }
}