python-3.x - getHeight 如何递归确定二叉树的高度？

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)

^{请注意，查找树高度的算法对于二叉搜索树和一般二叉树是相同的，因此出于讨论的目的，我将忽略 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}向报告高度 1 {5}，向{5}报告高度 2，向{3}报告{3}高度 3 {1}。最后，{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

python-3.x - getHeight 如何递归确定二叉树的高度？

问题描述

解决方案

推荐阅读