LeetCode 剑指 Offer 36. 二叉搜索树与双向链表

Categories:

Tags:

题目描述
思路分析
1. 解法一：中序遍历串联（推荐）
相似题目

题目描述

✅ 剑指 Offer 36. 二叉搜索树与双向链表

思路分析

解法一：中序遍历串联（推荐）

核心思路：

BST 的中序遍历是递增序列。

遍历过程中维护前驱节点 prev，将当前节点与前驱相连。

最后将头尾节点首尾相接，形成循环双向链表。

复杂度分析：

时间复杂度：O(n)，其中 n 表示节点数量。

空间复杂度：O(h)，其中 h 为树高度，递归栈占用。

class Solution {
    private Node prev = null;
    private Node head = null;

    public Node treeToDoublyList(Node root) {
        if (root == null) {
            return null;
        }

        dfs(root);
        head.left = prev;
        prev.right = head;
        return head;
    }

    private void dfs(Node node) {
        if (node == null) {
            return;
        }

        dfs(node.left);

        if (prev == null) {
            head = node;
        } else {
            prev.right = node;
            node.left = prev;
        }
        prev = node;

        dfs(node.right);
    }
}

func treeToDoublyList(root *Node) *Node {
	if root == nil {
		return nil
	}

	var head *Node
	var prev *Node

	var dfs func(*Node)
	dfs = func(node *Node) {
		if node == nil {
			return
		}
		dfs(node.Left)

		if prev == nil {
			head = node
		} else {
			prev.Right = node
			node.Left = prev
		}
		prev = node

		dfs(node.Right)
	}

	dfs(root)
	head.Left = prev
	prev.Right = head
	return head
}

相似题目

题目	难度	考察点
426. 将二叉搜索树转化为排序的双向链表	中等	中序遍历
538. 把二叉搜索树转换为累加树	中等	中序遍历
230. 二叉搜索树中第 K 小的元素	中等	中序遍历
98. 验证二叉搜索树	中等	中序遍历
173. 二叉搜索树迭代器	中等	中序遍历

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/61654325