如何处理python列表中的null（leetcode 104）

Question

我正在尝试在 python 中解决 Leetcode 104：https ://leetcode.com/problems/maximum-depth-of-binary-tree/

代码注释建议输入类型为 TreeNode。测试用例：root = [3,9,20,null,null,15,7]

我对输入的类型感到困惑。

1. 输入类型是列表还是“TreeNode”？TreeNode 甚至是一种类型吗？它与列表有何不同？

2. 我如何获得 len(root)？因为那里有空值，所以我无法使用 len(root)。当然，我可以将 null 转换为字符串“null”，但这感觉很糟糕。

（我想用几何级数来解决这个问题。这就是为什么我需要长度）

这是我写的代码。使用几何级数。S = (a1*(q**n) - a1)/(q-1) when q != 1. 结果是使用我的hacky方式将null变成字符串“null”并将root视为一个列表类型。

## a_1 = 1, 

## q = 2, 

## s = len(root) = (a1*q - a1)/(q-1) = (1*(2**n) - 1)/(2-1) 

## --> len(root) = (2**n)-1  --> solve n 

import numpy as np

def f(root):

    s = len(root)

    n = (np.log(s+1))/(np.log(2))

    return n

print f([3,9,20,"null","null",15,7])

Answer 1

如果您激活Python答案的代码类型，您将收到以下评论：# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = None[3,9,20,null,null,15,7]只是那棵树的线性描述，3第一个节点在哪里，有叶子9和20，然后9有叶子null和再次null（所以，没有叶子），20有叶子15和7。但是，如果他们希望您将线性树描述解析为表单，那么给您定义TreeNode并让您使用参数是没有意义root的TreeNode。所以，你的任务是，前往下你root.left和root.right递归和记录的最大深度。PS：如果您选择不同的编程语言，问题不会改变，所以我推断，它们意味着null以符号方式None在 Python 中实现它（特别是因为left并且right默认情况下None是TreeNode实现）。PPS：上述线性树描述的工作原理如下：您首先命名树的根元素 [3]之后，您制作当前树的快照并从左到右命名所有尚未命名的叶子。如果一片叶子是空的，你只需调用它null（Python 特定的：）None。重复 2 直到没有未命名的叶子

Answer 2

YesTreeNode是有效类型。它与列表完全不同。您可以TreeNode在页面顶部的评论中获得类型的定义。它有一个值（self.val）和一个左子和一个右子，它们也是TreeNodes（虽然没有明确说明，这是二叉树的定义）。该len()函数调用__len__()参数的方法。它可能没有在TreeNode.附注。当您尝试使用列表作为输入来解决练习时，您就错了。您应该使用给定的TreeNode类型。