非递归实现二叉树从根出发的最长偶值路径算法问询

嘿，我来帮你理清这个问题的思路！首先咱们先明确问题：你要找的是从根节点出发，沿着子节点延伸的路径中，所有节点值都是偶数的最长路径长度（示例里的长度3应该是指路径包含3个连续偶值节点）。结合你提到的「允许用两个队列」的要求，其实用**广度优先搜索（BFS）**会比Morris遍历更直观，完全能满足你的需求，咱们一步步拆解：

核心思路（双队列实现） #

我们可以用两个队列分别做两件事：

• 第一个队列node_queue：存储当前正在处理的、处于偶值路径上的节点
• 第二个队列length_queue：存储对应节点的「从根到该节点的偶值路径长度」

具体步骤如下：

1. 初始化：先检查根节点，如果根节点值是偶数，就把它加入node_queue，同时把路径长度1加入length_queue；如果根是奇数，那最长路径直接就是0，不用继续了。
2. 循环处理队列：
   • 每次从两个队列中分别取出队首的节点和对应的路径长度
   • 更新全局的最长路径长度
   • 检查当前节点的左孩子：如果左孩子值是偶数，就把它加入node_queue，并把路径长度+1后加入length_queue
   • 检查当前节点的右孩子：同理，偶值的话就加入队列，长度+1
3. 终止条件：当队列空了，就说明所有可能的偶值路径都遍历完了，返回全局最长长度即可

代码示例（Python） #

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

def longest_even_path(root):
    if not root:
        return 0
    
    max_length = 0
    node_queue = []
    length_queue = []
    
    # 根节点是偶数才启动遍历
    if root.val % 2 == 0:
        node_queue.append(root)
        length_queue.append(1)
        max_length = 1
    
    while node_queue:
        current_node = node_queue.pop(0)
        current_len = length_queue.pop(0)
        
        # 处理左子节点
        if current_node.left and current_node.left.val % 2 == 0:
            new_len = current_len + 1
            node_queue.append(current_node.left)
            length_queue.append(new_len)
            if new_len > max_length:
                max_length = new_len
        
        # 处理右子节点
        if current_node.right and current_node.right.val % 2 == 0:
            new_len = current_len + 1
            node_queue.append(current_node.right)
            length_queue.append(new_len)
            if new_len > max_length:
                max_length = new_len
    
    return max_length

关于你提到的Morris遍历的补充 #

如果你坚持想用Morris遍历，其实也可以实现，但会麻烦一些：

• 你需要在遍历过程中维护一个「当前偶值路径长度」的变量：当访问到偶值节点时，长度+1并更新最大值；当遇到奇值节点时，把长度重置为0。
• 但Morris遍历是中序遍历，会涉及到临时修改树的指针（创建右孩子的前驱节点），而且回溯时需要额外处理路径长度的重置，反而不如双队列的BFS方法直接清晰。

总结 #

双队列的BFS方法完美匹配你的需求：逻辑简单易懂，不需要修改树结构，还能准确跟踪每一条从根出发的偶值路径长度，完全能高效解决这个问题。

内容的提问来源于stack exchange，提问作者Mo. Mitwaly