剑指offer-二叉搜索树与双向链表

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

思路：中序遍历

ac代码：

 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 import java.util.ArrayList;
15 import java.util.List;
16 public class Solution {
17     public TreeNode Convert(TreeNode pRootOfTree) {
18         TreeNode p;
19         if(pRootOfTree==null)
20             return null;
21         dfs(pRootOfTree);
22         for(int i=0;i<list.size();i++){
23             p=list.get(i);
24             if(i!=0){
25                 p.left=list.get(i-1);
26             }else{
27                 p.left=null;
28             }
29             if(i!=list.size()-1){
30                 p.right=list.get(i+1);
31             }else{
32                 p.right=null;
33             }
34         }
35         return list.get(0);
36     }
37      List<TreeNode>list=new ArrayList<TreeNode>();
38     void dfs(TreeNode root){
39         if(root!=null){
40             dfs(root.left);
41             list.add(root);
42             dfs(root.right);
43         }
44     }
45 }