树中特定属性节点搜索及路径属性赋值的高效实现问询

首先得说，你选前序遍历的思路完全找对方向了——毕竟我们需要跟踪从根到当前节点的完整路径，前序的“根-左-右”顺序刚好能顺次维护这条路径。但你提到的FIFO队列其实不太适配这个场景：队列是先进先出，当你遍历完子节点回溯到父节点时，没法轻松把路径里的子节点移除，很难准确维护当前的路径状态。换成栈结构（后进先出）会更贴合路径的回溯需求，或者干脆用递归的调用栈来隐式维护路径，代码会更简洁。

下面给你两种高效的实现方案，分别适配不同的场景：

方案一：递归前序遍历（简洁易读，适合常规深度的树） #

利用递归本身的调用栈来维护路径，同时跟踪一个“激活标记”——一旦路径上出现过attr1=1的节点，后续所有节点的attr2直接设为1，不用再反复检查路径：

def mark_path_attr2(node, path_activated=False, path=None):
    if not node:
        return
    
    # 初始化路径列表（仅根节点触发）
    if path is None:
        path = []
    
    # 当前节点加入路径
    path.append(node)
    
    # 更新激活状态：要么之前已经激活，要么当前节点attr1=1
    current_activated = path_activated or (node.attr1 == 1)
    
    # 如果处于激活状态，直接设置当前节点的attr2
    if current_activated:
        node.attr2 = 1
    
    # 首次遇到attr1=1的节点时，把整个路径的节点attr2都设为1
    if node.attr1 == 1 and not path_activated:
        for n in path:
            n.attr2 = 1
    
    # 递归遍历左右子节点，传递激活状态
    mark_path_attr2(node.left, current_activated, path)
    mark_path_attr2(node.right, current_activated, path)
    
    # 回溯：把当前节点移出路径，保证分支间不干扰
    path.pop()

为什么高效？ #

• 激活状态一旦开启，后续所有子节点直接设置attr2，没有多余检查；
• 只有首次触发attr1=1的节点时，才会遍历一次路径设置所有祖先，避免重复操作；
• 时间复杂度是O(n)，每个节点最多被访问一次。

方案二：迭代前序遍历（避免递归栈溢出，适合深层树） #

如果你的树深度特别大（比如几万层），递归可能会触发栈溢出，这时候用迭代方式手动维护栈和路径：

def iterative_mark_path_attr2(root):
    if not root:
        return
    
    # 栈元素格式：(当前节点, 是否已处理, 激活状态, 当前路径)
    stack = [(root, False, False, [])]
    
    while stack:
        node, processed, activated, path = stack.pop()
        
        if not processed:
            # 第一次弹出，先处理当前节点
            path.append(node)
            new_activated = activated or (node.attr1 == 1)
            
            # 首次触发attr1=1时，全路径设置attr2
            if node.attr1 == 1 and not activated:
                for n in path:
                    n.attr2 = 1
            # 已激活状态下直接设置当前节点
            elif new_activated:
                node.attr2 = 1
            
            # 标记为已处理，重新压入栈（后续处理回溯）
            stack.append((node, True, new_activated, path))
            
            # 先压右子节点，再压左子节点（栈后进先出，保证前序顺序）
            if node.right:
                stack.append((node.right, False, new_activated, path.copy()))
            if node.left:
                stack.append((node.left, False, new_activated, path.copy()))
        else:
            # 回溯阶段，移除当前节点，保证路径正确
            path.pop()

注意事项： #

• 传递给子节点的路径需要复制一份，避免不同分支共享同一路径导致混乱；
• 用processed标记区分“首次访问”和“回溯清理”，确保路径维护准确。

额外优化：激活后的剪枝 #

一旦进入激活状态，后续所有子节点的attr2必然需要设置（因为它们的路径包含已激活的节点），这时候我们完全不需要再检查子节点的attr1，直接设置attr2并遍历即可，能节省一些判断开销。比如在递归方案中，激活状态下的子节点遍历可以简化为直接传递True状态，跳过attr1检查。

总的来说，你的前序遍历思路是正确的，只需要把容器从队列换成栈（或利用递归栈）就能很好地解决问题。上面的两种方案都能高效完成需求，具体选哪种取决于你的树的深度和代码风格偏好。

内容的提问来源于stack exchange，提问作者Code Pope