二叉搜索树转单向链表—leetcode BiNode python实现

1.题目

二叉树数据结构TreeNode可用来表示单向链表（其中left置空，right为下一个链表节点）。实现一个方法，把二叉搜索树转换为单向链表，要求依然符合二叉搜索树的性质，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。

返回转换后的单向链表的头节点。

示例：

输入： [4,2,5,1,3,null,6,0]
输出： [0,null,1,null,2,null,3,null,4,null,5,null,6]
提示：

节点数量不会超过 100000。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binode-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

根据二叉搜索树的定义，左侧结点值小于中间结点值， 中间结点值小于右侧结点值，所以依次访问结点并转换为列表时服从左中右的顺序，即符合中序遍历方法。两个指针，prev指向前驱结点（上一个结点），cur指向当前结点

2.堆栈法

使用堆栈通过空间换时间

代码如下：

class Solution:
    def convertBiNode(self, root: TreeNode) -> TreeNode:
        if not root:
            return root
        head = TreeNode(None)
        prev = head
        stack = []
        cur = root
        # 栈里还有元素没添加到链表
        while stack or cur:
            # 当cur有左子树，左子树及根节点入栈
            while cur:
                stack.append(cur)
                cur = cur.left
            # 跳出while循环的cur是没有左子树的cur
            # if not cur:
            cur = stack.pop()
            cur.left = None
            prev.right = cur
            prev = cur
            cur = cur.right
                
        return head.right

通过新生成一个head结点，用来快速获取头结点，方便输出。

head = TreeNode(None)

通过第一个while循环遍历子树中的所有结点

while stack or cur:

通过第二个while循环，获取树中的"左侧结点"，并入栈，直到达到该子树的最左侧结点，跳出循环时cur = None

while cur:
     stack.append(cur)
     cur = cur.left

顶部元素出栈，并对cur赋值

cur = stack.pop()

要注意对cur.left赋空值，否则生成的链表会是一个’‘双向链表’’， 原本存在的left指针和新添加的right指针在遍历时会陷入死循环。

这里想了很久即使是双链表为什么会超时死循环呢？个人分析是leetcode该题的输出会自动遍历链表，从而陷入死循环，不然的话单纯输出一个结点不至于死循环。

通过prev.right连接新的cur节点，再将prev指向新的cur节点，完成传递，最后cur = cur.right会遍历当前结点的右节点，符合中序遍历顺序。
当右节点不存在时，又会从stack中pop出存储的左侧结点和中间结点

cur.left = None
prev.right = cur
prev = cur
cur = cur.right

3.中序遍历-迭代法

代码如下：

class Solution:
    def convertBiNode(self, root: TreeNode) -> TreeNode:
        self.head = TreeNode(None)
        self.prev = self.head
        def convert(root):
            if root:
                convert(root.left)
                root.left = None
                self.prev.right = root
                self.prev = root
                convert(root.right)
                # root = root.right
        convert(root)
        return self.head.right 

思路与第一种方法类似，中序遍历，单独定义个函数负责遍历。
通过convert依次访问所有结点，并将其与prev相连接传递。
这里使用self.head和self.prev在类的对象中定义参数，这样在convert函数中不需要再另外赋值。

同样head表示头结点，方便输出。

先找左子树中最左结点，直到为None，将左指针赋空

def convert(cur):
	if cur:
		convert(cur.left)
		cur.left = None
		self.prev.right = cur
		self.prev = cur
		convert(cur.right)

经过这个迭代操作，左指针连接的结点要么为空要么已经被遍历过，再赋空值不会有影响。

convert(cur.left)

总结

这道题考察了二叉树的中序遍历操作，

def inOrder(root):	
	if root:
		inOrder(root.left)
		print(root.val) 
		inOrder(root.right)
	else:
		return None

链表的基本连接操作，即

prev.next = cur
prev = cur
cur = cur.next

虽然简单题，但很多细节没注意花了很久参考了别人的代码才通过，还需努力。