为什么我的 tree-node 函数在我 运行 通过它时生成一个数组?
Why is my tree-node function producing Null when I run an array through it?
我正在研究 LeetCode 问题 104. Maximum Depth of Binary Tree:
Given the root
of a binary tree, return its maximum depth.
A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
我的尝试无效:我首先将 root
添加到队列中(如果 root
不是 None
),然后通过添加其 child重新排队。
在做这个的时候,我保留了一个计数器,每添加一个child节点,我就将计数器加1。当左右child都存在时,我只会增加计数器加 1.
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def max_depth(self,root):
counter = 1
queue = deque
if not root:
return 0
else:
queue.append(root)
while queue:
root = queue.popleft()
if root.left:
queue.append(root.left)
counter +=1
if root.right:
queue.append(root.right)
if root.left:
continue
else:
counter +=1
return counter
然而,当我在 LeetCode 上 运行 上面的内容时,输入 [3,9,20,null,null,15,7],结果是 'None' .
是不是因为我构造了函数不以列表作为输入?
Is it because I have structured the function to not take a list as an input?
没有。这可能令人困惑,但在 LeetCode 上,输入的原始列表表示在调用函数之前会转换为 TreeNode
的实例。所以你永远不必处理这个列表结构。它只是 LeetCode 在不同编程语言中使用的通用输入格式。但是在调用您的实现之前,已经为您完成了到目标语言数据结构的转换。
您的代码在第一次调用 queue.append
时产生错误,因为这一行:
queue = deque
这是错误的,因为这使得 queue
成为 class deque
的同义词。但它应该是它的一个实例,所以:
queue = deque()
通过该修复,函数不会 return None
。
但是,它的逻辑是不正确的:
I keep a counter, and each time I add a child node, I increment the counter by 1. When both left and right child exist, I will only increment the counter by 1.
这实际上意味着您计算至少有一个子节点的节点数,即您计算树的 internal 节点数。
这是不正确的。例如,下面的树有 7 个内部节点:
___ 10 __
/ \
5 14
/ \ / \
1 8 12 20
/ \ / \ / \ / \
0 2 6 9 11 13 18 22
显然,7 不是正确答案。在这种情况下应该是 4。
您的基于队列的解决方案将逐层访问节点,但您没有关于何时从一个级别传递到下一个级别的任何信息。
您可以使用两个(标准)列表来解决这个问题:第一个列表将包含一个级别的所有节点,第二个列表将收集下一个级别的所有节点。完成后,您知道您已经处理了一个级别。然后你把第二个列表放在第一个,然后清空第二个。然后只要有节点需要处理就可以重启这个进程:
class Solution:
def maxDepth(self, root: TreeNode) -> int:
counter = 0
queue = []
if root:
queue.append(root)
while queue:
counter +=1
nextlevel = []
for root in queue:
if root.left:
nextlevel.append(root.left)
if root.right:
nextlevel.append(root.right)
queue = nextlevel
return counter
让它更紧凑一点,可以是:
class Solution:
def maxDepth(self, root: TreeNode) -> int:
counter = 0
if root:
queue = [root]
while queue:
counter +=1
queue = [root.left for root in queue if root.left
] + [root.right for root in queue if root.right]
return counter
您也可以进行深度优先遍历,而不是您想要的广度优先遍历:
class Solution:
def maxDepth(self, root: TreeNode) -> int:
return 1 + max(self.maxDepth(root.left),
self.maxDepth(root.right)) if root else 0
我正在研究 LeetCode 问题 104. Maximum Depth of Binary Tree:
Given the
root
of a binary tree, return its maximum depth.A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
我的尝试无效:我首先将 root
添加到队列中(如果 root
不是 None
),然后通过添加其 child重新排队。
在做这个的时候,我保留了一个计数器,每添加一个child节点,我就将计数器加1。当左右child都存在时,我只会增加计数器加 1.
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def max_depth(self,root):
counter = 1
queue = deque
if not root:
return 0
else:
queue.append(root)
while queue:
root = queue.popleft()
if root.left:
queue.append(root.left)
counter +=1
if root.right:
queue.append(root.right)
if root.left:
continue
else:
counter +=1
return counter
然而,当我在 LeetCode 上 运行 上面的内容时,输入 [3,9,20,null,null,15,7],结果是 'None' .
是不是因为我构造了函数不以列表作为输入?
Is it because I have structured the function to not take a list as an input?
没有。这可能令人困惑,但在 LeetCode 上,输入的原始列表表示在调用函数之前会转换为 TreeNode
的实例。所以你永远不必处理这个列表结构。它只是 LeetCode 在不同编程语言中使用的通用输入格式。但是在调用您的实现之前,已经为您完成了到目标语言数据结构的转换。
您的代码在第一次调用 queue.append
时产生错误,因为这一行:
queue = deque
这是错误的,因为这使得 queue
成为 class deque
的同义词。但它应该是它的一个实例,所以:
queue = deque()
通过该修复,函数不会 return None
。
但是,它的逻辑是不正确的:
I keep a counter, and each time I add a child node, I increment the counter by 1. When both left and right child exist, I will only increment the counter by 1.
这实际上意味着您计算至少有一个子节点的节点数,即您计算树的 internal 节点数。 这是不正确的。例如,下面的树有 7 个内部节点:
___ 10 __
/ \
5 14
/ \ / \
1 8 12 20
/ \ / \ / \ / \
0 2 6 9 11 13 18 22
显然,7 不是正确答案。在这种情况下应该是 4。
您的基于队列的解决方案将逐层访问节点,但您没有关于何时从一个级别传递到下一个级别的任何信息。
您可以使用两个(标准)列表来解决这个问题:第一个列表将包含一个级别的所有节点,第二个列表将收集下一个级别的所有节点。完成后,您知道您已经处理了一个级别。然后你把第二个列表放在第一个,然后清空第二个。然后只要有节点需要处理就可以重启这个进程:
class Solution:
def maxDepth(self, root: TreeNode) -> int:
counter = 0
queue = []
if root:
queue.append(root)
while queue:
counter +=1
nextlevel = []
for root in queue:
if root.left:
nextlevel.append(root.left)
if root.right:
nextlevel.append(root.right)
queue = nextlevel
return counter
让它更紧凑一点,可以是:
class Solution:
def maxDepth(self, root: TreeNode) -> int:
counter = 0
if root:
queue = [root]
while queue:
counter +=1
queue = [root.left for root in queue if root.left
] + [root.right for root in queue if root.right]
return counter
您也可以进行深度优先遍历,而不是您想要的广度优先遍历:
class Solution:
def maxDepth(self, root: TreeNode) -> int:
return 1 + max(self.maxDepth(root.left),
self.maxDepth(root.right)) if root else 0