题解 | #二叉搜索树与双向链表#

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

#
# 
# @param pRootOfTree TreeNode类 
# @return TreeNode类
#
class Solution:
    def PreNode(self, root : TreeNode):
        this = root
        if not this:
            return None
        if this.left:
            this = this.left
            while this.right:
                this = this.right
            root.left = this
            this.right = root
    def RearNode(self, root : TreeNode):
        this = root
        if not this:
            return None
        if this.right:
            this = this.right
            while this.left:
                this = this.left
            root.right = this
            this.left = root
    def LDR(self, this : TreeNode):
        if this:
            self.LDR(this.left)
            # 遍历完左孩子后，左指针解放,于是可以将左指针指向前驱
            self.PreNode(this)

            self.LDR(this.right)
            # 遍历完右孩子后，右指针解放,于是可以将右指针指向后继
            self.RearNode(this)

    def Convert(self , pRootOfTree ):
        # write code here
        this = pRootOfTree
        if not this:
            return None
        # 找到最小节点，作为头节点
        while this.left:
            this = this.left
        head = this
        self.LDR(pRootOfTree)
        return head