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

[songyy5517]

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

为了让您更好地理解问题，以下面的二叉搜索树为例：

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

分析 这道题主要考察的是二叉搜索树和双向链表的性质。一个很直接的想法是二叉搜索树的中根遍历序列是递增的，因此需要对二叉搜索树进行中根遍历。难点是如何将二叉搜索树转换成双向链表。方法是通过中根遍历序列构建双向链表，依次将遍历到的节点加入双向链表中。 为什么一开始没想到？当时看到条件 “要求不能创建任何新的节点，只能调整树中节点指针的指向。”，就想着如何调整节点指针的方向，断开这重连那的，增加了解题的难度，完全没有必要。只要根据中根遍历序列，依次将遍历到的节点加入双向链表中即可。

[songyy5517]

思路：中序遍历的同时完成转换

1. 定义全局变量分别记录双向链表的头节点 head 和当前链表的尾节点 tail，并初始化成null；

2. 定义递归方法：中序遍历二叉树，并将其转换成双向链表： （1）递归出口：当前节点为空时，返回； （2）递归遍历左子树； （3）判断双向链表当前尾节点是否为空：（！）

   • 若为空，则说明当前节点为链表首节点，将head和tail都置成当前节点；
   • 否则，将当前节点添加到链表尾部。

   （4）递归遍历右子树；

(4. 处理双向链表的首尾节点）

5. 在主方法中调用递归方法；
6. 返回头节点head；

复杂度分析：

• 时间复杂度 O(N)：N为二叉树的节点数，中序遍历需要访问所有节点。
• 平均空间复杂度 $O(\log N)$ ：平均情况下，递归深度为树的深度 $\log_2 N$ ，系统使用 $O(\log N)$ 栈空间。
• 最坏空间复杂度 O(N)：最差情况下，即树退化为链表时，递归深度达到N，系统使用 O(N) 栈空间。

[songyy5517]

import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }
}  
*/
public class Solution {
    TreeNode head = null;    // 当前双向链表的头节点
    TreeNode tail = null;    // 当前双向链表的尾节点
    public TreeNode Convert(TreeNode pRootOfTree) {
        // 思路：中根遍历二叉搜索树，依次将遍历到的节点插入双向链表中。
        // 调用递归方法
        midRootTraverse(pRootOfTree);
        // 返回链表头节点
        return head;
    }

    void midRootTraverse(TreeNode root){
        // 递归出口
        if (root == null)
            return;

        // 遍历左子树
        midRootTraverse(root.left);

        // 若当前双向列表的首尾节点都为空，则当前节点为链表首节点
        if (head == null || tail == null){
            head = root;
            tail = root;
        }
        // 否则将当前节点加入双向链表中
        else {
            tail.right = root;
            root.left = tail;
            tail = root;
        }
        // 遍历右子树
        midRootTraverse(root.right);
    }
}

[songyy5517]

基于队列的中序遍历：

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
    public Node treeToDoublyList(Node root) {
        // 思路：基于队列的中根遍历
        // 1. 异常处理
        if (root == null)
            return null;

        // 2. 创建队列保存中根序列
        Queue<Node> queue = new LinkedList();
        midOrder(root, queue);

        // 3. 根据中根序列队列，将节点转换为双向列表
        Node head = queue.remove();
        Node tail = head;
        Node cur = null;

        while (!queue.isEmpty()){
            cur = queue.remove();
            tail.right = cur;
            cur.left = tail;
            tail = cur;
        }

        // 4. 处理首尾节点
        head.left = tail;
        tail.right = head;

        return head;
    }

    void midOrder(Node root, Queue queue){
        // 1. 递归出口
        if (root == null)
            return;

        midOrder(root.left, queue);
        queue.add(root);
        midOrder(root.right, queue);
    }
}

[songyy5517]

2023/2/2

1. 全局变量无需作为递归方法的形参

2024/1/30

1. 构造完头节点后，不能直接返回。

2024/2/28

1. 可以将递归方法与主方法进行合并；
2. 无需再创建新节点，可以直接对原来的节点进行操作。