我是 Python 新手,遇到了一些问题。我正在使用 Python 3。
我已将此逻辑用于二叉搜索树以获取其高度:
class Node:
def __init__(self, data):
self.right = self.left = None
self.data = data
class Solution:
def insert(self, root, data):
if root is None:
return Node(data)
else:
if data > root.data:
cur = self.insert(root.right, data)
root.right = cur
else:
cur = self.insert(root.left, data)
root.left = cur
return root
def getHeight(self, root):
# Write your code here
if root is None:
return 0
else:
return 1 + max(self.getHeight(root.right), self.getHeight(root.left))
T = int(input())
myTree = Solution()
root = None
for i in range(T):
data = int(input())
root = myTree.insert(root, data)
height = myTree.getHeight(root)
print(height)
有了这个输入:
7
3
5
2
1
4
6
7
第一个7是节点数。
但我得到的是四个而不是三个,并且在示例中说高度必须是三个。
我做错了什么?
注意:我的代码只在 getHeight
方法上。
最佳答案
您可以根据插入逻辑绘制树来手工检查您的答案
level1 3
level2 2 5
level3 1 4 6
level4 7
如果您正在计算边,那么是的,它是三,但树的高度显然是四。
在基本情况下,您可以通过 return -1
解决措辞不佳的问题
关于python - 获取二叉搜索树的高度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46022032/