展平二叉树解释

Question

我正在尝试解决有关将二叉树展平为链表类型结构的问题。我也会在这里写下问题描述

编写一个函数，接收二叉树，将其展平，然后返回其最左边的节点。扁平二叉树是一种与双向链表几乎相同的结构（除了节点具有左和右） 指针而不是上一个和下一个指针），其中节点遵循原始树从左到右的顺序。请注意，如果输入的二叉树恰好是有效的二叉搜索树，则展平树中的节点将被排序。扁平化应该就地完成，这意味着原始数据结构应该被改变。每个二叉树节点都有一个整数值、一个左子节点和一个右子节点。子节点可以是 BinaryTree 节点本身，也可以是 None / null。

我的代码：

class BinaryTree:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


def flattenBinaryTree(root):
    a, b = helper(root)
    return a
    pass


def helper(node):
    if node is None:
        return None, None
    if node.left is None and node.right is None:
        return node, node
    print(node.value)
    leftmostofleft = node
    rightmostofright = node
    leftmostofright = None
    rightmostofleft = None
    if node.left:
        leftmostofleft, rightmostofleft = helper(node.left)
    if node.right:
        leftmostofright, rightmostofright = helper(node.right)

    node.right = leftmostofright
    if leftmostofright:
        leftmostofright.left = node
    node.left = rightmostofleft
    if rightmostofleft:
        rightmostofleft.right = node

    return leftmostofleft, rightmostofright

我的问题

我放在这里的代码有效。但我不明白的问题是在这些行中。

leftmostofleft = node
rightmostofright = node
leftmostofright = None
rightmostofleft = None

这些是默认值，以防节点没有左侧或右侧。所以，我想如果节点根本没有左子树或子树，那么最左边的节点将与右边的节点相同。但我不明白的是为什么 leftmostofright 和 rightmostofleft 必须是 None 。他们不应该也是节点吗？因为子树的最左边或右边的值也是节点的值？ 简而言之，如果我将上面的代码块更改为这样

leftmostofleft = node
rightmostofright = node
leftmostofright = node
rightmostofleft = node

这不起作用。我确实认为如果我这样做的话可能会创建重复项，但如果可能的话我想要一个解释？

测试代码

import program
import unittest


class TestProgram(unittest.TestCase):
    def test_case_1(self):
        root = BinaryTree(1).insert([2, 3, 4, 5, 6])
        root.left.right.left = BinaryTree(7)
        root.left.right.right = BinaryTree(8)
        leftMostNode = program.flattenBinaryTree(root)
        leftToRightToLeft = leftMostNode.leftToRightToLeft()
        expected = [4, 2, 7, 5, 8, 1, 6, 3, 3, 6, 1, 8, 5, 7, 2, 4]
        self.assertEqual(leftToRightToLeft, expected)


class BinaryTree(program.BinaryTree):
    def insert(self, values, i=0):
        if i >= len(values):
            return
        queue = [self]
        while len(queue) > 0:
            current = queue.pop(0)
            if current.left is None:
                current.left = BinaryTree(values[i])
                break
            queue.append(current.left)
            if current.right is None:
                current.right = BinaryTree(values[i])
                break
            queue.append(current.right)
        self.insert(values, i + 1)
        return self

    def leftToRightToLeft(self):
        nodes = []
        current = self
        while current.right is not None:
            nodes.append(current.value)
            current = current.right
        nodes.append(current.value)
        while current is not None:
            nodes.append(current.value)
            current = current.left
        return nodes

Answer 1

当您分配

leftmostofright = node

时，当该节点没有右子节点时，您将在执行此分配时创建一个循环：

node.right = leftmostofright

这显然不是你想要发生的事情。当节点没有右子节点时，您不想给它一个右子节点。只有

None

是

node.right

的正确值。

其他一些备注：

• 不需要将叶节点与其他节点区别对待。所以你可以省略

  if node.left is None and node.right is None:

  块。

• 当节点没有左子节点时，您实际上不需要分配给

  node.left

  。没有右孩子时也一样。

• 您可以不使用

  leftmostofright

  和

  rightmostofleft

  ，只需将这些引用 直接 分别分配给

  node.left

  和

  node.right

  。

所以你的

helper

代码可以简化为这样：

def helper(node):
    leftmost = node
    rightmost = node
    if node and node.left:
        leftmost, node.left = helper(node.left)
        node.left.right = node
    if node and node.right:
        node.right, rightmost = helper(node.right)
        node.right.left = node
    return leftmost, rightmost