二叉排序树转双向链表

编程练习

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

思路：考虑先采用遍历二叉排序树，再对排序后的二叉树序列排序，最后增加每个节点的前向后向指针即可。

java代码如下：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
	public  TreeNode Convert(TreeNode pRootOfTree) {
		if(pRootOfTree==null){
			return null;
		}  
		ArrayList<Integer> valList=PrintFromTopToBottom(pRootOfTree);
		valList.sort(null);
		System.out.println(valList);
		ArrayList<TreeNode> convertList=new ArrayList<TreeNode>();
		for(int i: valList) {
			convertList.add(new TreeNode(i));
		}
		if(convertList.size()==1) {
			return convertList.get(0);
		}
		//处理端点处的情况
		convertList.get(0).left=null;
		convertList.get(0).right=convertList.get(1);
		convertList.get(convertList.size()-1).right=null;
		convertList.get(convertList.size()-1).left=convertList.get(convertList.size()-2);
		//处理中间的双向链表，添加指针
		for(int i=1;i<convertList.size()-1;i++) {
			convertList.get(i).left=convertList.get(i-1);
			convertList.get(i).right=convertList.get(i+1);
		}
		
		return convertList.get(0);
	}
	public  ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
		Queue<TreeNode> treeQueue=new LinkedList<TreeNode>();
		ArrayList<Integer> valList=new ArrayList<Integer>();
		
		if(root==null) {
			return valList;
		}
		
		treeQueue.add(root);
		
		while(!treeQueue.isEmpty()) {
			TreeNode node=treeQueue.poll();
			valList.add(node.val);
			if(node.left!=null) {
				treeQueue.add(node.left);
			}
			if(node.right!=null) {
				treeQueue.add(node.right);
			}
		}
		
		return valList;
	}	
}