python-3.x - 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 以计算此特定递归调用考虑的当前节点的高度 plus 以当前节点为根的左右子树高度的最大值。这是关键的递归步骤。

让我们来看看对上面示例树的 height 的调用。

我们首先访问节点 {1} 作为我们的根。这不是基本情况，因此 {1} 向其左子 {2} 询问其最大高度。 {2} 也不是基本情况，因此它向其左 child None 询问其总数。 None 是我们的第一个基本情况，将 0 返回给 {2}。 {2} 然后询问其右 child {4} 的高度。 {4} 是一个带有两个返回 0 的空 None 引用的叶子，但是 {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} 向 报告高度 2 {3} 和 {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