二叉搜索树与双向链表

二叉搜索树与双向链表_牛客题霸_牛客网

问题简述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。

思路

• 二叉搜索树的中序遍历结果即为有序链表；

• 使用一个全局变量记录上一个节点，记 pre；

• 到每个节点时，修改 pre 和当前节点的指向；

• 因为二叉树的遍历都只会访问节点一次，因此中序时修改节点的 left 指向不会影响后序的遍历结果；

• 注意保存最左边的节点；

Python

class Solution:
    def Convert(self , pRootOfTree ):
        
        from dataclasses import dataclass
        
        # 其实就是两个全局变量
        @dataclass
        class Info:
            pre = None  # 保存上一个节点
            ret = None  # 保存最右侧节点
        
        def dfs(x, info):
            if not x: return info
            
            dfs(x.left, info)
            if not info.pre:  # 头结点
                info.ret = x
            else:
                x.left = info.pre
                info.pre.right = x
            info.pre = x
            dfs(x.right, info)
            return info
        
        return dfs(pRootOfTree, Info()).ret