Java实题演练二叉搜索树与双向链表分析

题目描述

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

思路分析

对于一颗二叉搜索树，有以下性质：

1. 若左子树不为空，则左子树上所有结点的值均小于它的根结点的值；
2. 若右子树不为空，则右子树上所有结点的值均大于它的根结点的值；
3. 左右子树也为二叉搜索树。

我们考虑中序遍历该二叉搜索树，得到的序列就是一个有序序列。因此，我们可以中序遍历二叉树，遍历过程中将当前节点的left指针指向前一个节点，将前一个节点的right指针指向当前节点，最后返回第一个节点即可。

代码实现

public TreeNode treeToDoublyList(TreeNode root) {
    if (root == null) return null;

    TreeNode first = null;
    TreeNode last = null;

    helper(root, first, last);

    // 处理首尾相连的情况
    last.right = first;
    first.left = last;

    return first;
}

private void helper(TreeNode node, TreeNode first, TreeNode last) {
    if (node == null) return;

    // 中序遍历
    helper(node.left, first, last);

    // 处理当前节点
    if (last != null) {
        last.right = node;
        node.left = last;
    } else {
        first = node;
    }
    last = node;

    helper(node.right, first, last);
}

示例说明

示例一：

输入：

    4
   / \
  2   5
 / \
1   3

输出：

1<->2<->3<->4<->5

示例二：

输入：

    2
   / \
  1   3

输出：

1<->2<->3