LeetCode二叉搜索树转循环双链表Python代码报错排查

题目要求 #

原地将二叉搜索树转换为排序循环双链表。可将节点的left、right指针对应双链表的前驱、后继指针；循环双链表中首节点的前驱为尾节点，尾节点的后继为首节点。

当前已实现的版本自测时值的顺序、双向指向的输出值看似正确，但提交始终报错：

链表[1,2,3,4,5]不是有效的循环双链表。

原有问题代码 #

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inOrderTraversal(node, array):
    if node == None:
        return

    inOrderTraversal(node.left, array)
    array.append(node.val)
    inOrderTraversal(node.right, array)
    return array


class Solution:
    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if root is None:
            return None
        array = []
        inOrderTraversal(root, array)

        head = Node(array[0])
        head.left = Node(array[-1])
        prev_node = head

        for i in range(1, len(array)):
            num = array[i]
            node = Node(num)


            prev_node.right = node     
            node.left = prev_node
            prev_node = node

            if i == len(array) - 1:
                node.right = head


        count = 0
        node = head
        while count < 5:
            print("new Test")
            print(node)
            print(node.left.val)
            print(node.right.val)
            node = node.right
            count += 1

       # print(head.right.val)

        return head

调试输出 #

new Test
<__main__.Node object at 0x7f0318a062c0>
5
2
new Test
<__main__.Node object at 0x7f0318a06a40>
1
3
new Test
<__main__.Node object at 0x7f0318a06c20>
2
4
new Test
<__main__.Node object at 0x7f0318a3e680>
3
5
new Test
<__main__.Node object at 0x7f0318a3e6e0>
4
1

错误原因 #

你的代码有两个核心问题，直接导致校验不通过：

• 违反原地修改要求：题目要求直接调整原树节点的指针完成转换，你在中序遍历拿到节点值后，全部新建了Node对象拼接链表，完全没有复用原二叉树的节点，测试框架校验节点身份时会直接判定结果无效。
• 循环链路断裂：你给头节点设置left指针时，单独新建了一个值为5的节点，这个节点和循环最后生成的值为5的尾节点根本不是同一个对象；同时你只给尾节点设置了right指向头节点，既没有把尾节点的left正确指向值为4的前序节点，也没有把头节点的left指向真正的尾节点，只是指向了一个孤立的值为5的新节点，不满足循环双链表的双向闭环要求。
  你的调试输出只打印了节点的val，没有发现两个值为5的节点内存地址完全不同，看起来值是对的，实际指针连的是完全不相关的对象。

修正后可通过代码 #

不用改动整体逻辑，只需要把中序遍历存节点值改为存原节点引用，全程不新建Node对象即可：

class Solution:
    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if root is None:
            return None
        node_list = []
        # 中序遍历直接存储原树节点
        def inOrder(node):
            if not node:
                return
            inOrder(node.left)
            node_list.append(node)
            inOrder(node.right)
        inOrder(root)

        head = node_list[0]
        prev = head
        for i in range(1, len(node_list)):
            cur = node_list[i]
            prev.right = cur
            cur.left = prev
            prev = cur
        # 首尾相连形成闭环
        tail = prev
        head.left = tail
        tail.right = head
        return head

内容的提问来源于stack exchange，提问作者young_coder