二叉搜索树与双向链表

题目描述

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

后序遍历，最后来改根节点的指针，递归的思路

public TreeNode Convert(TreeNode pRootOfTree) {
    TreeNode head = null;
    if (pRootOfTree == null) {
        return head;
    }

    TreeNode leftHead = Convert(pRootOfTree.left);
    TreeNode rightHead = Convert(pRootOfTree.right);


    pRootOfTree.left = null;
    if (rightHead != null) {
        pRootOfTree.right = rightHead;
        rightHead.left = pRootOfTree;
    } else {
        pRootOfTree.right = null;
    }
    head = pRootOfTree;

    if (leftHead != null) {
        TreeNode tn = leftHead;
        for (; tn.right != null; tn = tn.right) {
        }
        tn.right = pRootOfTree;
        pRootOfTree.left = tn;
        head = leftHead;
    }
    return head;
}