题解 | 二叉搜索树与双向链表

二叉搜索树的中序遍历是有序的，因此通过中序遍历来递归二叉树。

flatten方法：

• 按照中序遍历的顺序，先递归处理左子树。
• 处理当前节点，将其连接到双向链表中。
• 如果 tail 不为 null，说明已经有节点在链表中，此时将当前节点的左指针指向 tail，tail 的右指针指向当前节点。
• 如果 tail 为 null，说明找到最左侧的节点，即最小值为头节点，将head指向当前节点。
• 更新 tail 为当前节点。
• 最后递归处理右子树。

import java.util.*;

public class Solution {
    // 用于记录双向链表的头节点
    public TreeNode head = null;
    // 用于记录双向链表的尾节点
    public TreeNode tail = null;

    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }
        // 进行中序遍历并构建双向链表
        flatten(pRootOfTree);
        return head;
    }

    // 中序遍历二叉树并构建双向链表
    public void flatten(TreeNode cur) {
        if (cur == null) {
            return;
        }
        // 递归处理左子树
        flatten(cur.left);

        // 处理当前节点，将其连接到双向链表中
        if (tail != null) {
            // 当前节点的左指针指向前驱（即tail）
            cur.left = tail;
            // 前驱的右指针指向当前节点
            tail.right = cur;
        } else {
            // 找到最左侧的节点，即最小值为头节点
            head = cur;
        }
        // 更新尾节点为当前节点
        tail = cur;
        // 递归处理右子树
        flatten(cur.right);
    }
}