getHeight如何递归地确定二叉树的高度

Question

我真的不理解计算二叉树高度的代码背后的逻辑。如果有人理解它，你能用一种简单的方式解释吗？

我试图通过放置断点来理解，但逻辑对我来说仍然不清楚

import pdb
class Node:
def __init__(self,data):
self.right=self.left=None
self.data = data
#print(self.data)
class Solution:  #creating and inserting the nodes
def insert(self,root,data):
#print(data)
if root==None:
return Node(data)
else:
if data<=root.data:
cur=self.insert(root.left,data)
root.left=cur
else:
cur=self.insert(root.right,data)
root.right=cur
return root
def getHeight(self,root): #finding the height of the largest 
branchintree
#Write your code here
if not root:
return -1
if not root.left and not root.right:
return 0
left_height=self.getHeight(root.left)
#print('left_height',left_height)
right_height=self.getHeight(root.right)
#print('right_height',right_height)
r=max(left_height,right_height) + 1
#print('r',r)
return max(left_height,right_height) + 1


T=int(input())
pdb.set_trace()
myTree=Solution()
root=None
for i in range(T):
data=int(input())
root=myTree.insert(root,data)
height=myTree.getHeight(root)
print(height)

Answer 1

^{请注意，查找树高度的算法对于二进制搜索树和一般二进制树是相同的，因此出于本讨论的目的，我将忽略BST}

---

这个代码不是特别清楚，所以我不怪你不理解它。

这里有一个重写来减少噪音：

from collections import namedtuple
Node = namedtuple("Node", "data left right")
def height(root): 
return max(height(root.left), height(root.right)) + 1 if root else 0
#      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^         ^^^^^^     
#      |                                          |           |
#      |                                          |           base case; root is None
#      |                                          add the current node's height
#      recursively find the maximum height of the current node's children

if __name__ == "__main__":
"""     1 
/   
2     3
    /
4  5

6 
"""
root = Node(
1,
Node(
2,
None,
Node(4, None, None)
),
Node(
3,
Node(
5,
None,
Node(6, None, None)
),
None
)
)
print(height(root)) # => 4

现在，在对height的给定调用中，我们有两种情况：

• root是None，在这种情况下，我们返回0，因为我们什么都没有。这是我们的基本情况，或者终止递归的条件
• root不是None，在这种情况下，我们返回1，以计算此特定递归调用所考虑的当前节点的高度加上植根于当前节点的左子树和右子树的最大高度。这是关键的递归步骤

让我们在上面的示例树上遍历对height的调用。

我们首先访问节点{1}作为我们的根。这不是一个基本情况，所以{1}会询问其左子{2}的最大高度。{2}也不是一个基本情况，所以它向它的左子None询问它的总数。None是我们的第一个基本情况，并将0返回给{2}。{2}然后询问其右侧子对象{4}的身高。{4}是一个具有两个空None引用的叶，这些引用返回0，但{4}为其自身添加1并将其返回给{2}。

节点{2}现在可以计算max(height(root.left), height(root.right))，即max(0, 1) => 1，并且{2}可以加1来计算其自身的高度，并向{1}报告其总计2。

我们的根{1}的左子树现在的高度为2，但它还没有检查右子树，所以max(height(root.left), height(root.right))必须等待。

对于{1}的右子树，过程基本相同：如果节点不是叶节点，它会询问其子节点各自的高度，并取最大值，加1计算自身，并向父节点报告。在这种情况下，{6}向{5}报告高度1，{5}向{3}报告高度2，{3}向{1}报告高度3。最后，{1}可以计算出max(2, 3)，并为自己的高度加1，将4的最终结果返回给调用者。

如果所有这些都有点抽象，那么您总是可以使用递归调用来添加depth参数并打印其状态。

from collections import namedtuple
Node = namedtuple("Node", "data left right")
def height(root, depth=0): 
if root:
print(" " * depth + f"{{{root.data}}} asking children...")
left_height = height(root.left, depth + 4)
right_height = height(root.right, depth + 4)
ret = max(left_height, right_height) + 1
print(" " * depth + f"{{{root.data}}} reporting max({left_height}, {right_height}) + 1 = {ret}")
return ret
print(" " * depth + "None returning 0")
return 0

if __name__ == "__main__":
"""     1 
/   
2     3
    /
4  5

6 
"""
root = Node(
1,
Node(
2,
None,
Node(4, None, None)
),
Node(
3,
Node(
5,
None,
Node(6, None, None)
),
None
)
)
print(height(root)) # => 4

输出：

{1} asking children...
{2} asking children...
None returning 0
{4} asking children...
None returning 0
None returning 0
{4} reporting max(0, 0) + 1 = 1
{2} reporting max(0, 1) + 1 = 2
{3} asking children...
{5} asking children...
None returning 0
{6} asking children...
None returning 0
None returning 0
{6} reporting max(0, 0) + 1 = 1
{5} reporting max(0, 1) + 1 = 2
None returning 0
{3} reporting max(2, 0) + 1 = 3
{1} reporting max(2, 3) + 1 = 4
4