二叉搜索树与双向链表

题目描述

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

思路

1. 使用递归算法求解。

2.使用两个TreeNode分别存储前一个结点（pre）以及头结点（head）。

3.每个递归方法中，将当前node结点与pre结点进行相连。

node.left = pre
pre.right = node

4.当递归到最左侧的叶子结点时，将其值赋值给head即可。（二叉搜索树最左边的叶子结点的值是最小的）

Java代码实现

public class Solution {

    private TreeNode head;
    private TreeNode pre;

    public TreeNode Convert(TreeNode pRootOfTree) {
        reverse(pRootOfTree);
        return head;
    }

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

}