题目:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。
思路:利用中序遍历的方法递归遍历二叉树,把二叉树拆分为左子树、根节点、右子树三部分,再连接起来。第一步先遍历左子树转化为链表,然后把根节点连在左子树的最后节点,然后再递归遍历右子树。
测试用例:
1. 功能测试:完全二叉树;所有节点只有左子树的二叉树;所有节点只有右子树的二叉树;只有一个节点。
2. 特殊测试:输入的根节点为空。
public class test_thirty_six {
TreeNode tail = null; //定义链表的最后一个节点
TreeNode head = null; //链表的第一个节点
public TreeNode Convert(TreeNode pRootOfTree) {
ConvertSub(pRootOfTree);
return head;
}
//构造一个递归函数中序遍历二叉树
private void ConvertSub(TreeNode pRootOfTree) {
if(pRootOfTree==null) return;
ConvertSub(pRootOfTree.left); //递归遍历左子树
if (tail == null) { //左子树为空
tail = pRootOfTree; //根节点即为尾节点
head = pRootOfTree;
}
else {
tail.right = pRootOfTree; //把根节点连接到左子树的末尾
pRootOfTree.left = tail;
tail = pRootOfTree; //更新尾节点
}
ConvertSub(pRootOfTree.right); //递归遍历右子树
}
}