36. 二叉搜索树与双向链表

Leetcode

题目描述

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

解题思路

二叉搜索树的中序遍历是升序的，因此按中序遍历节点，用 pre 记录上一个访问的节点，访问 node 时把两者双向连起来：node.left = pre，pre.right = node。第一个访问的节点（最小值）就是链表头 head；遍历结束后 pre 指向最大的节点，再把 head 与 pre 首尾相连，得到循环双向链表。

修改指针不会影响遍历：改 node.left 时左子树已经遍历完，改 pre.right 时 pre 的右子树也已经遍历完或正在遍历（node 就在其中）。

private Node pre = null;
private Node head = null;

public Node treeToDoublyList(Node root) {
    if (root == null)
        return null;
    head = null;
    pre = null;
    inOrder(root);
    head.left = pre;
    pre.right = head;
    return head;
}

private void inOrder(Node node) {
    if (node == null)
        return;
    inOrder(node.left);
    node.left = pre;
    if (pre != null)
        pre.right = node;
    pre = node;
    if (head == null)
        head = node;
    inOrder(node.right);
}