二叉搜索树与双向链表

二叉搜索树：左节点值<根值<右节点值。将其转化为排序的双向链表，链表中每个TreeNode的left节点指向比自己小的TreeNode，right节点指向比自己大的TreeNode，最后得到的链表序列是树中序遍历序列，然后把每个节点的左右孩子指向正确的节点即可。

解法一：将树的中序遍历结果存入一个队列，依次出队构建双向链表。

 1 import java.util.LinkedList;
 2 
 3 public class Solution{
 4 　　public TreeNode Convert(TreeNode pRootOfTree) {
 5 　　　　if(pRootOfTree == null)return null;
 6 　　　　TreeNode pHead,p,temp;
 7 　　　　LinkedList<TreeNode> lTree = new LinkedList<TreeNode>();
 8 　　　　ConvertTree(pRootOfTree,lTree);
 9 　　　　pHead = lTree.removeFirst();pHead.left = null;
10 　　　　p = pHead;temp = pHead;
11 　　　　while(!lTree.isEmpty()){
12 　　　　　　temp = lTree.removeFirst();
13 　　　　　　p.right = temp;
14 　　　　　　temp.left = p;
15 　　　　　　p = temp;        
16 　　　　}
17 　　　　temp.right = null;
18 　　　　return pHead;
19 　　}
20 　　public void ConvertTree(TreeNode pRoot,LinkedList<TreeNode> lTree){
21 　　　　if(pRoot == null)return ;
22 　　　　if(pRoot.left!=null)
23 　　　　　　ConvertTree(pRoot.left,lTree);
24 　　　　lTree.add(pRoot);
25 　　　　if(pRoot.right!=null)
26 　　　　　　ConvertTree(pRoot.right,lTree);         
27 　　}
28 　}

解法二：递归构造。

 1 public class Solution {
 2 　　public TreeNode Convert(TreeNode pRootOfTree) {
 3 　　　　if(pRootOfTree == null)return null;
 4 　　　　ConvertTree(pRootOfTree);
 5 　　　　TreeNode  p = pRootOfTree,q=pRootOfTree;
 6 　　　　while(q.left!=null){          
 7 　　　　　　q = q.left;           
 8 　　　　}
 9 　　　　while(p.right!=null){          
10 　　　　　　p = p.right;          
11 　　　　}
12 　　　　return q;
13 　　}
14 　　public void ConvertTree(TreeNode pRoot){       
15 　　　　TreeNode pleft ,pright,left= pRoot.left,right = pRoot.right;
16 　　　　if(pRoot.left == null) pleft = null;
17 　　　　else{          
18 　　　　　　pleft = pRoot.left;
19 　　　　　　while(pleft.right!=null)
20 　　　　　　　　pleft = pleft.right;           
21 　　　　　　}
22 　　　　if(pRoot.right == null) pright = null;
23 　　　　else{
24 　　　　　　pright = pRoot.right;
25 　　　　　　while(pright.left!=null)
26 　　　　　　　　pright = pright.left;
27 　　　　}      
28 　　　　pRoot.left = pleft;
29 　　　　pRoot.right = pright;
30 　　　　if(left!=null)
31 　　　　　　ConvertTree(left);
32 　　　　if(right!=null)
33 　　　　　　ConvertTree(right);
34 　　　　if(pleft!=null)pleft.right = pRoot;
35 　　　　if(pright!=null)pright.left = pRoot;
36 　　}
37 }

注意：在确定了一个节点的左右节点的指向后，不能直接将左孩子的右节点和右孩子的左节点指向根，应该在该节点的左右子树完成向双向链表的转化后再进行。