如何通过一个函数调用更新二叉树中所有节点的高度？

Question

我有一个由 class:

节点组成的二叉树

class Node:
    def __init__(self,key,parent=None,right=None,left=None):
        self.key = key
        self.left = left
        self.right = right
        self.parent = parent
        self.height = 0

树构造的示例可以是：

a = Node(1)
a.left = Node(2,parent=a)
a.right = Node(5,parent=a)
a.right.right = Node(3,parent=a.right)

我想编写一个函数来更新这棵树中所有节点的高度。我找到了获取一个节点高度的方法。但是，我想一次更新所有高度。

我该怎么做？

Answer 1

您可以添加这个递归方法：

def syncheight(self):
    self.height = max(
        -1 if self.left is None else self.left.syncheight(), 
        -1 if self.right is None else self.right.syncheight()
    ) + 1
    return self.height

您可以按如下方式在根上调用它：

a.syncheight()

请注意，我会调用 class Node 而不是 node，并且您的参数名称与您在构造函数主体中使用的名称不同（left, leftChild)

建议

我不会将 parent 传递给构造函数，因为这应该遵循作为 left 和 right 传递的信息。后者应该更新它们的 parent 属性以引用当前创建的节点。

然后您还可以通过更新新创建节点的祖先的高度来保持 height 更新：

class Node:
    def __init__(self, key, left=None, right=None):
        self.key = key
        self.left = left
        self.right = right
        self.parent = None
        if left:
            left.parent = self
        if right:
            right.parent = self
        self.height = -1
        self.bubbleheight()
    
    def bubbleheight(self):
        height = max(
            -1 if self.left is None else self.left.height,
            -1 if self.right is None else self.right.height
        ) + 1
        if height != self.height:
            self.height = height
            if self.parent is not None:
                self.parent.bubbleheight()

tree = Node(1,
            Node(2),
            Node(5,
                Node(3)
            )
        )

print(tree.height)  # 2

如何通过一个函数调用更新二叉树中所有节点的高度？

How to update height of all nodes in a binary tree with one function call?

python

binary-tree

建议