题目: 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。
解法:
private static TreeNode pre = null;//记录最后一个尾节点
private static TreeNode head = null;//记录双向链表头结点
public static TreeNode Convert(TreeNode pRootOfTree) {
ConvertCore(pRootOfTree);
return head;
}
private static void ConvertCore(TreeNode node) {//中序遍历二叉搜索树即为有序
if (node == null)
return;
ConvertCore(node.left);
node.left = pre;
if (pre != null)
pre.right = node;
pre = node;
if (head == null)
head = node;
ConvertCore(node.right);
}
网友评论