Question

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

思路：线索化二叉树。类似于中序遍历构建。

由于正向构建时，指针会移动到尾部，因此反向构建。

public class Solution {
  TreeNode pre = null;
  public TreeNode Convert(TreeNode pRootOfTree) {
    if(pRootOfTree == null) return null;
    Convert(pRootOfTree.right);
    if(pre!=null){
      pRootOfTree.right = pre;
      pre.left = pRootOfTree;
    }
    pre = pRootOfTree;
    Convert(pRootOfTree.left);
    return pre;
  }
}