Anytree二叉树快速层级遍历优化求助：解决21层树遍历性能问题

问题根源分析 #

你当前方案的核心性能瓶颈在于：

• 多次调用LevelOrderIter遍历子树，21层二叉树有超过200万节点，每次遍历子树都是O(n)级别的开销；
• 使用集合去重后再排序，集合操作和排序的时间复杂度随剩余节点数增长，叠加后导致总耗时剧增。

解决方案 #

方案1：利用节点descendants属性+单次层序遍历 #

anytree的每个AnyNode自带descendants属性，可以直接获取该节点的所有后代节点（无需再次调用LevelOrderIter），配合单次层序遍历+跳过集合，能大幅降低耗时：

from anytree import LevelOrderIter

listfar = []
# 记录需要跳过的节点ID，避免重复处理
skipped_ids = set()

for node in LevelOrderIter(root):
    if node.id in skipped_ids:
        continue
    # 替换为你的条件判断逻辑
    if 节点满足条件:
        # 收集当前节点+所有后代的ID
        descendant_ids = [n.id for n in node.descendants]
        listfar.append([node.id] + descendant_ids)
        # 将后代ID加入跳过集合，后续遍历直接跳过
        skipped_ids.update(descendant_ids)

这个方案只需要遍历整棵树一次，descendants的获取是基于节点内部父子关系的直接遍历，比重新调用LevelOrderIter快数倍，集合判断是O(1)操作，总时间复杂度为O(n)，200万节点的遍历+处理完全能在1秒内完成。

方案2：手动维护队列，跳过满足条件节点的子树 #

如果不需要预存所有待处理节点，直接用队列实现层序遍历，遇到满足条件的节点就跳过其子节点，完全避免冗余遍历：

from collections import deque

listfar = []
queue = deque([root])

while queue:
    node = queue.popleft()
    # 替换为你的条件判断逻辑
    if 节点满足条件:
        # 收集当前节点+所有后代的ID
        descendant_ids = [n.id for n in node.descendants]
        listfar.append([node.id] + descendant_ids)
        # 不将子节点加入队列，直接跳过后续遍历
        continue
    # 不满足条件，将子节点加入队列继续遍历
    if hasattr(node, 'left') and node.left:
        queue.append(node.left)
    if hasattr(node, 'right') and node.right:
        queue.append(node.right)

这个方案的效率最高，因为它只遍历需要处理的节点，一旦遇到满足条件的节点，直接跳过其所有子树，无需再遍历这些节点，内存占用也更小。

针对你的问题的直接回答 #

1. 快速生成后代ID列表：anytree节点的descendants属性可以直接获取所有后代节点，在此基础上提取ID即可，比LevelOrderIter快得多；
2. 保持顺序移除节点：不要用集合去重再排序的方式，而是用跳过集合标记需要排除的节点，在遍历过程中直接跳过，或者直接采用队列遍历的方式，从根源避免维护待处理列表的问题。

内容的提问来源于stack exchange，提问作者Teo Georgatos