算法刷题Day8：BM30 二叉搜索树与双向链表

题目

牛客网题目传送门

思路

对二叉搜索树进行中序遍历，结果就是按序数组。因此想办法把前面遍历过的节点给记下来，记作pre。当遍历到某个节点node的时候，令前驱指向pre，然后让pre的后驱指向node。

代码

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None  # 前驱
        self.right = None  # 后驱
class Solution:
    def __init__(self):
        self.pre = TreeNode(-1)
        self.first = TreeNode(-1)

    def Traverse(self, root):
        if root == None:
            return
        self.Traverse(root.left)
        root.left = self.pre
        self.pre.right = root
        self.pre = root
        self.Traverse(root.right)
        return

    def Convert(self, pRootOfTree):
        if pRootOfTree == None:
            return pRootOfTree
        # 找到最左边的节点
        def findLeft(root):
            node = root
            while node.left is not None:
                node = node.left
            return node
        self.first = findLeft(pRootOfTree)
        # 中序遍历
        self.Traverse(pRootOfTree)
        self.first.left = None //把头结点的前驱置为None
        return self.first

芜湖，明天要去玩了，顺便把明天的卡也做了。经前综合征在我26岁的时候，爆发到了极值。绝了。怎么感觉除了经期，其他时期也稍微就正常一点，经常忘事，和导师吐槽了一下自己的记忆力，然后导师安慰我说：这是正常~ 本科期间丢了7张校卡，总是忘记哈哈哈，短期记忆是真的不行。（谢谢导师，导师对我真的好包容）。当然，记忆力这是可以锻炼的，或者拿本本记下来。off course,当忘记事情的时候，也不要过于责怪自己。