26、二叉搜索树与双向链表

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

==========Python==========

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

#
# 
# @param pRootOfTree TreeNode类 
# @return TreeNode类
#
class Solution:
    def __init__(self):
        self.head = None
        self.pre = None
    def Convert(self , pRootOfTree ):
        # write code here
        def dfs(pRootOfTree):
            if pRootOfTree is None:
                return
            dfs(pRootOfTree.left)
            pRootOfTree.left = self.pre
            if self.pre:
                self.pre.right = pRootOfTree
            self.pre = pRootOfTree
            if self.head is None:
                self.head = pRootOfTree
            dfs(pRootOfTree.right)
        
        dfs(pRootOfTree)
        return self.head

==========Java=========

public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode (int val) {
        this.val = val;
    }
}

public class Solution {
    private TreeNode head = null;
    private TreeNode pre = null;

    public TreeNode Convert(TreeNode root) {
        ConvertHelper(root);
        return head;
    }

    private void ConvertHelper(TreeNode node) {
        if (node == null) {
            return;
        }
        ConvertHelper(node.left);
        node.left = pre;
        if (pre != null) {
            pre.right = node;
        }
        pre = node;
        if (head == null) {
            head = node;
        }
        ConvertHelper(node.right);
    }


}