如何通过单次遍历计算树中每个节点的高度

核心思路 #

节点高度的通用定义为：当前节点到其下属最远叶子节点的最长路径包含的边数（部分场景会把路径上的节点数作为高度，仅需调整初始值即可，逻辑完全一致）。
要做到每个节点仅访问1次，核心是选对遍历顺序：节点高度依赖其所有子节点的高度值，因此只要按「先处理完所有子节点，再处理当前节点」的顺序遍历，就能在不重复访问的前提下算完全部高度，最直接的实现就是后序深度优先遍历（DFS）。

具体实现逻辑 #

• 遍历顺序严格遵循后序规则：先递归遍历当前节点的所有子节点，待所有子节点的高度计算完成后，再计算当前节点的高度。
• 存储方式：可以用哈希表绑定节点和对应的高度值，如果业务允许修改节点属性，也可以直接把高度值挂在节点对象的自定义属性上，无需额外存储结构。
• 递归终止条件：遇到空节点时直接返回基准值（按边数算高度返回-1，按节点数算高度返回0），不需要额外访问空节点。

代码参考（Python版） #

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def calculate_all_heights(root):
    node_height = {}
    def post_order_traverse(node):
        # 空节点直接返回基准高度，无额外访问开销
        if not node:
            return -1
        # 先算所有子节点高度，每个子节点仅进入一次递归
        left_child_height = post_order_traverse(node.left)
        right_child_height = post_order_traverse(node.right)
        # 当前节点高度为子节点最大高度+1
        current_height = max(left_child_height, right_child_height) + 1
        node_height[node] = current_height
        return current_height
    
    post_order_traverse(root)
    return node_height

补充说明 #

• 如果递归深度过大会触发栈溢出，可以替换为迭代版后序遍历，手动维护栈结构和节点访问标记，依然能保证每个节点仅入栈、出栈各1次，访问次数不超过1次。
• 该方案时间复杂度为O(n)（n为树的总节点数），空间复杂度最坏为O(n)（树退化为单链表的场景），平衡树场景下空间复杂度为O(logn)，是该问题的最优解法。
• 也可以从叶子节点出发做类拓扑排序的层序遍历（从下往上逐层更新父节点高度），本质和后序逻辑一致，但实现复杂度更高，没有特殊需求优先选后序DFS即可。

内容的提问来源于stack exchange，提问作者Nahuel Marrero