题目:
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。
思路:
使用中序遍历的思路进行解题,定义两个引用初始化指向根节点.
private TreeNode tempNode;
private TreeNode head;
public TreeNode Convert(TreeNode pRootOfTree){
ConvertSub(pRootOfTree);
return head;
}
private void ConvertSub(TreeNode pRootOfTree){
if(pRootOfTree == null)
return ;
if(pRootOfTree.left != null)
ConvertSub(pRootOfTree.left);
//这段代码仅执行依次在初始化的执行
if(tempNode == null){
tempNode = pRootOfTree;
head = pRootOfTree;
}else{
tempNode.right = pRootOfTree;
pRootOfTree.left = tempNode;
tempNode = pRootOfTree;
}
if(pRootOfTree.right != null){
ConvertSub(pRootOfTree.right);
}
}