[数据结构与算法]Sword36——二叉搜索树与双向链表

Sword36——二叉搜索树与双向链表

方法1——递归/中序遍历

• 思路：看到二叉搜索树，肯定需要利用其特点，又因为其中转换为排序的循环双向链表，即证明要使用中序遍历，因为中序遍历的结果恰好为有序。如果恰好能每次遍历到一个节点时，都记录前一个节点和当前节点，则可以在遍历中完成调整。每次递归完成后已经获取到前一个节点和当前节点，进行构造即可
• 特殊情况与临界分析：根节点非空判断
• 终止条件：最后一个节点完成转换即可
• 步骤：
  • 定义全局使用的前一个节点和链表头节点
  • 根节点非空判断
  • 展开递归
  • 构造头节点和尾节点的关系
    • 头节点的left指向尾节点
    • 尾节点的right指向头节点
  • 返回头节点
  • 递归方法
    • 参数：当前节点
    • 终止条件：当前节点为空
    • 对其左子树递归
    • 当pre非空时，证明当前节点不是根节点，需要将前一节点的right指向当前节点
    • 否则当pre为空时，证明当前节点为根节点，即head记录链表头节点
    • 当前节点的left指向前一个节点
    • 前一个节点后移，即记录当前节点
    • 对其右子树递归

	// 定义全局的前一个节点、链表头节点
	Node pre, head;
	public Node treeToDoublyList(Node root) {
        // 根节点非空判断
        if (root == null) {
            return null;
        }
        // 展开递归，中序遍历
        dfs(root);
        // 构造头尾节点的关系
        head.left = pre;
        pre.right = head;
        // 返回链表头节点
        return head;
    }
	// 递归方法
	private void dfs(Node cur) {
        // 终止条件：当前节点为空
        if (cur == null) {
            return;
        }
        // 对其左子树递归
        dfs(cur.left);
        // 当pre非空时，证明当前遍历节点并非根节点，需要将pre的right指向当前节点
        if (pre != null) {
            pre.right = cur;
        // 当pre为空时，证明当前遍历节点为根节点，即head记录此节点
        } else {
            head = cur;
        }
        // 当前节点的left指向前一个节点
        cur.left = pre;
        // pre后移，即记录当前节点
        pre = cur;
        // 对其右子树递归
        dfs(cur.right);
    }