题目

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

思路

  本题又出现了，二叉搜索树，如果是按照顺序刷下来的话。我们就知道，搜索二叉树的性质：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。

  对二叉搜索树更一步的了解。不妨看看JZ23—二叉搜索树的后续遍历序列

  有了这样一个前提思想，我们利用二叉搜索树构建一个排序的双向链表就很好做了。合理利用它的性质，使用中序遍历那么就是一个排好序的二叉树。我们再使用递归构建出来即可。

AC代码

/** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { TreeNode node = null; TreeNode t = null; TreeNode flag = null; public TreeNode Convert(TreeNode pRootOfTree) { if(pRootOfTree == null) return null; f(pRootOfTree); return flag; } public void f(TreeNode pRootOfTree){ if(pRootOfTree == null) return ; f(pRootOfTree.left); // 初始化阶段 if(node == null){ node = pRootOfTree; flag = node; t = pRootOfTree; }else{ // 构建这样一个双向链表 node.right = pRootOfTree; node.right.left = t; node = node.right; t = t.right; } f(pRootOfTree.right); } }