一、题目
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
二、解法
1 /**
2 public class TreeNode {
3 int val = 0;
4 TreeNode left = null;
5 TreeNode right = null;
6
7 public TreeNode(int val) {
8 this.val = val;
9
10 }
11
12 }
13 */
14 public class Solution {
15 public TreeNode Convert(TreeNode pRootOfTree) {
16 if(pRootOfTree == null)
17 return null;
18 //如果是叶子结点
19 if(pRootOfTree.left == null && pRootOfTree.right == null)
20 return pRootOfTree;
21 //1、先从左子树遍历
22 TreeNode left = Convert(pRootOfTree.left);
23 TreeNode p = left;//p指向当前链表的最后一个结点
24 while(p != null && p.right != null)
25 p = p.right;
26 //2、与当前的pRootOfTree进行连接
27 //p.right = pRootOfTree; pRootOfTree.left = p;
28 if(left != null){
29 p.right = pRootOfTree;
30 pRootOfTree.left = p;
31 }
32 //3、右子树转换为双向链表
33 TreeNode right = Convert(pRootOfTree.right);
34 if(right != null){
35 pRootOfTree.right = right;
36 right.left = pRootOfTree;
37 }
38 return left != null ? left : pRootOfTree;
39 }
40 }