二叉搜索树与双向链表（Java）

题目：

输入一颗二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向，比如输入下图中左边的二叉搜索树，则输出转换之后的排序双向链表。

struct BinaryTreeNode{
	int m_nValue;
	BinaryTreeNode* m_pLeft;
	BinaryTreeNode* m_pRight;
}

思路1：

在二叉树中，每个结点都有两个指向子结点的指针。在双向链表中，每个结点也有两个指针，它们分别指向前一个结点和后一个结点。故链表和二叉搜索树的结构是相似的。在二叉搜索树中，左子结点的值总是小于父结点的值，右子结点的值总是大于父结点的值。因此在转换成排序双向链表时，原先指向左子结点的指针调整为链表中指向前一个结点的指针，原先指向右子结点的指针调整为链表中指向后一个结点的指针。

要求转换之后是有序的，我们知道二叉搜索树的中序遍历结果也是有序的。当中序遍历到根结点的时候，我们把二叉搜索树看成3部分：值为10的结点，根结点为6的左子树，根结点为14的右子树。根据排序链表的定义，值为10的结点将和它的左子树的最大一个结点值为8的结点链接起来，同时它还将和右子树中最小的结点值为12的结点链接起来。如下图：

注：根结点、左子树、右子树。在把左右子树都转换成排序的双向链表之后再和根结点链接起来，整颗二叉搜索树也就转换成了排序的双向链表

按照中序递归遍历中，当我们遍历转换到根结点时，它的左子树已经转换成了一个排序的链表，并且此时链表尾部的值为左子树中值最大的结点的值（8）。我们将它（8）和根结点（10）链接起来，此时根结点（10）变成了链表尾部，接着去遍历右子树，我们知道中序遍历根结点（10）后的一个结点此时为右子树值最小的结点（12），我们将它和根结点链接起来。左右子树再用这样的办法，即递归即可解决问题。

代码实现：

public class BinaryTreeNode {

	public int m_nValue;
	
	public BinaryTreeNode m_pLeft;
	
	public BinaryTreeNode m_pRight;
	
}

public class Main2 {

	BinaryTreeNode head = null; //定义链表当前结点
	BinaryTreeNode realHead = null; //定义链表头部的结点
	//中序递归遍历修改链表指针即可实现
	public BinaryTreeNode convert(BinaryTreeNode pRootOfTree){
		if(pRootOfTree == null){
			return null;
		}
		convert(pRootOfTree.m_pLeft); //左
		 
		if(head == null){ //根
			head = pRootOfTree;
			realHead = pRootOfTree;
		}else{
			head.m_pRight = pRootOfTree;
			pRootOfTree.m_pLeft = head;
			head = pRootOfTree;
		}
		
		convert(pRootOfTree.m_pRight); //右
		return realHead;
	}
	//main方法测试
	public static void main(String[] args) {
		Main2 m2 = new Main2();
		BinaryTreeNode node1 = new BinaryTreeNode();
		node1.m_nValue = 1;
		
		BinaryTreeNode node2= new BinaryTreeNode();
		node2.m_nValue = 2;
		
		BinaryTreeNode node3 = new BinaryTreeNode();
		node3.m_nValue = 3;
		   
		node2.m_pLeft = node1;
		node2.m_pRight = node3;
		BinaryTreeNode head = m2.convert(node2);
		System.out.println(head.m_nValue);
		System.out.println(head.m_pRight.m_nValue);
		System.out.println(head.m_pRight.m_pRight.m_nValue);
	}
}

思路2：非递归借助栈实现

我们借助一个栈实现二叉树非递归的中序遍历，并修改其结点的指针实现双向排序的链表。

代码实现：

public BinaryTreeNode convert(BinaryTreeNode pRootOfTree){
	if(pRootOfTree == null){
		return null;
	}
	BinaryTreeNode list = null;
	Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
	while(pRootOfTree != null || !stack.isEmpty()){
		if(pRootOfTree!=null){
			stack.push(pRootOfTree);
			pRootOfTree = pRootOfTree.m_pRight;
		}else{
			pRootOfTree = stack.pop();
			if(list == null){
				list = pRootOfTree;
			}else{
				list.m_pLeft = pRootOfTree;
				pRootOfTree.m_pRight = list;
				list = pRootOfTree;
			}
			pRootOfTree = pRootOfTree.m_pLeft;
		}
	}
	return list;
}

小思：

感觉在考查我们二叉搜索树中序遍历和双向排序的链表之间的关系，以及怎么去修改二叉搜索树的指针。