二叉搜索树库在我自己的IDE上测试leetcode

Question

我目前正在做一道有关 leet 代码的 BST 问题，但我更喜欢在自己的 IDE 上做。我正在使用 IntelliJ IDEA。一个例子是 leet code 的问题是求最大路径和。

我的代码如下：

# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right

class Solution(object):
    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """

        def maxSum(root, max_sum=0):
            if root is None:
                return max_sum

            left_root = root.left.val
            right_root = root.right.val
            final_sum = left_root + right_root + root.val
            if final_sum > max_sum:
                max_sum = final_sum
                maxSum(root, max_sum)

        return maxSum(root)


print(Solution().maxPathSum(root=[-10, 9, 20, None, None, 15, 7]))

我的代码中有一些错误，我无法测试它们，因为我习惯了我的树节点输入如下：

test_tree_node = BST(20)
test_tree_node.insert(5)
test_tree_node.insert(23)

leet 代码中给出的输入（测试用例）是一个数组。我需要导入什么库才能测试它们？ （这样 root.left 和 root.right 就可以工作等）。

对于我上面提到的 BST，它看起来像这样：

class BST:
    def __init__(self, value, depth=1):
        self.value = value
        self.depth = depth
        self.left = None
        self.right = None

    def insert(self, value):
        if value < self.value:
            if self.left is None:
                self.left = BinarySearchTree(value=value, depth=self.depth + 1)
                print(f'Tree node {value} added to the left of {self.value} at depth {self.depth + 1}')
            else:
                self.left.insert(value)
        else:
            if self.right is None:
                self.right = BinarySearchTree(value=value, depth=self.depth + 1)
                print(f'Tree node {value} added to the right of {self.value} at depth {self.depth + 1}')
            else:
                self.right.insert(value)

    def get_node_by_value(self, value):
        if value == self.value:
            return self
        elif self.left and value < self.value:
            return self.left.get_node_by_value(value)
        elif self.right and value >= self.value:
            return self.right.get_node_by_value(value)
        else:
            return None

    def depth_first_traversal(self):
        if self.left is not None:
            self.left.depth_first_traversal()
        print(f'Depth={self.depth}, Value={self.value}')
        if self.right is not None:
            self.right.depth_first_traversal()

Answer 1

首先，您正在查看的代码挑战不是您所说的“BST 问题”：它不会给您一个二叉 search 树，也不打算成为一棵，而只是一棵二叉树，所以你的

BST

类在这里基本上是不相关的。

您需要在这里使用的唯一类是

TreeNode

类，它在顶部的评论部分中给出：

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

因此，在 IDE 中要做的第一件事就是取消注释，以便定义上述类。

现在主要问题：LeetCode 使用的格式是类似 JSON 的输入，看起来像 Python 中的列表，但实际上是文本格式（注意它如何使用

null

而不是

None

）。在调用函数之前，LeetCode 平台会将此文本输入转换为

TreeNode

的（嵌套）实例。

要根据 Python 列表作为输入来模拟该过程，您可以使用此函数：

def to_binary_tree(items):
    if not items:
        return None

    it = iter(items)
    root = TreeNode(next(it))
    q = [root]
    for node in q:
        val = next(it, None)
        if val is not None:
            node.left = TreeNode(val)
            q.append(node.left)
        val = next(it, None)
        if val is not None:
            node.right = TreeNode(val)
            q.append(node.right)
    return root

现在您可以通过执行以下操作来运行解决方案代码：

lst = [-10, 9, 20, None, None, 15, 7]
root = to_binary_tree(lst)
print(Solution().maxPathSum(root))

最后，你的

maxSum

函数没有做正确的事情。它所做的唯一一件事就是对三个节点的值求和：根节点及其两个直接子节点的值。递归调用将第二次进行相同的计算，并得出结论：这不是改进，并且返回

None

（隐式）。所以

maxPathSum

将返回

None

。由于您的问题是关于将列表转换为树，我将把这个问题留给您进一步的分析和开发。