二叉搜索树与双向链表

题目描述

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

///////////////////////////////////////////////////////////////

下午有点晕晕的，感觉不太好，改了改也算是过了，

中序遍历，一开始不知道如何判断是该返回root左边的还是右边的节点，所以加了一个flag判断一下，

如果flag=1，说明对于上一层节点，这是左子树，那么返回root最右边的节点，

如果flag=2，说明对于上一层，这是右子树，那么返回root最左边的节点，

flag=0，说明到了根节点那里，返回最左边的节点就是链表最开始的节点了。

******************************************************************************************

后来我看了解答，发现好像返回谁都行，因为你返回以后，上一层的root节点接收你返回的节点，如果这是左子树返回的，那么找到最后就是要连接的节点了

如果是右子树返回的，那么找到最左边的那个，就是root后面要跟着的节点了。

//还有一些细节比如为空之类的就不提了

 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         return helper(pRootOfTree,0);
19     }
20     public TreeNode helper(TreeNode root,int flag)
21     {
22         if(root==null)
23             return null;
24         TreeNode left=helper(root.left,1);
25         if(left==null)
26             root.left=left;
27         else
28         {
29             root.left=left;
30             left.right=root;
31         }
32         TreeNode right=helper(root.right,2);
33         if(right==null)
34             root.right=right;
35         else
36         {
37             root.right=right;
38             right.left=root;
39         }
40         if(flag==1)
41         {
42             TreeNode res=root;
43             while(res.right!=null)
44                 res=res.right;
45             return res;
46         }
47         else if(flag==2)
48         {
49             TreeNode res=root;
50             while(res.left!=null)
51                 res=res.left;
52             return res;
53         }
54         else
55          {
56             TreeNode res=root;
57             while(res.left!=null)
58                 res=res.left;
59             return res;
60         }
61     }
62 }