题目：
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
思路一：递归法
1.将左子树构造成双链表，并返回链表头节点。
2.定位至左子树双链表最后一个节点。
3.如果左子树链表不为空的话，将当前root追加到左子树链表。
4.将右子树构造成双链表，并返回链表头节点。
5.如果右子树链表不为空的话，将该链表追加到root节点之后。
6.根据左子树链表是否为空确定返回的节点。
class Untitled {
public static void main(String[] args) {
TreeNode node1 = new TreeNode(10);
TreeNode node2 = new TreeNode(6);
TreeNode node3 = new TreeNode(14);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(8);
TreeNode node6 = new TreeNode(12);
TreeNode node7 = new TreeNode(16);
node1.setNode(node2,node3);
node2.setNode(node4,node5);
node3.setNode(node6,node7);
Solution s = new Solution();
TreeNode p = s.Convert(node1);
while(p.right!=null){
System.out.println(p.val);
p = p.right;
}
}
}
//树的定义
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
public void setNode(TreeNode node1,TreeNode node2){
this.left = node1;
this.right = node2;
}
}
//解方法
class Solution {
public TreeNode Convert(TreeNode root) {
if(root==null)
return null;
if(root.left==null&&root.right==null)
return root;
// 1.将左子树构造成双链表，并返回链表头节点
TreeNode left = Convert(root.left);
TreeNode p = left;
// 2.定位至左子树双链表最后一个节点
while(p!=null&&p.right!=null){
p = p.right;
}
// 3.如果左子树链表不为空的话，将当前root追加到左子树链表
if(left!=null){
p.right = root;
root.left = p;
}
// 4.将右子树构造成双链表，并返回链表头节点
TreeNode right = Convert(root.right);
// 5.如果右子树链表不为空的话，将该链表追加到root节点之后
if(right!=null){
right.left = root;
root.right = right;
}
return left!=null?left:root;
}
}
思路二：
如果知道二叉搜索树的中序遍历是有序列的话，那么这道题的方法也就呼之欲出了
public class Solution {
TreeNode realHead = null;
TreeNode head = null;
public TreeNode Convert(TreeNode root) {
ConvertHelp(root);
return realHead;
}
public void ConvertHelp(TreeNode root){
if(root==null)
return;
ConvertHelp(root.left);
if(realHead==null){
head = root;
realHead = root;
}else{
head.right = root;
root.left = head;
head = root;
}
ConvertHelp(root.right);
}
}
由于中序遍历的特点，第一次碰到的绝对是最左下的结点，因此可以将头节点赋给他。