求二叉树中所有可能路径的最大乘积：算法伪代码编写求助

嘿，我来帮你搞定这个二叉树路径最大乘积的伪代码难题！先把问题拆解清楚：我们要遍历所有从根到叶子的路径，计算每条路径上节点值的乘积，最终找出最大的那个结果。而且节点值可能是正、负甚至零，这几个情况得特别留意——比如负数相乘说不定会从负转正，零的话直接把乘积置零，这些都得在算法里考虑到。

核心思路 #

最适合这个问题的遍历方式是深度优先搜索（DFS），不管是递归还是迭代实现都能轻松覆盖所有根到叶子的路径。我们需要在遍历过程中跟踪两个关键值：

• 当前路径的乘积
• 遍历至今找到的最大乘积

递归版伪代码 #

递归写法逻辑最直观，代码量也少：

// 用一个变量保存全局最大乘积，初始设为负无穷（应对全负数路径的情况）
max_product = -∞

// 递归函数：传入当前节点和当前路径的乘积
function dfs(node, current_product):
    if node is null:
        return
    
    // 更新当前路径乘积：乘以当前节点的值
    current_product = current_product * node.value
    
    // 到达叶子节点时，更新最大乘积
    if node.left is null and node.right is null:
        if current_product > max_product:
            max_product = current_product
        return
    
    // 递归遍历左右子树
    dfs(node.left, current_product)
    dfs(node.right, current_product)

// 主函数入口
function maxPathProduct(root):
    if root is null:
        return 0  // 空树情况根据题目要求调整，比如返回null或者0
    
    // 初始化最大乘积为负无穷
    max_product = -∞
    // 初始乘积设为1，这样第一个节点值乘以1就是自身，逻辑正确
    dfs(root, 1)
    return max_product

递归代码解释 #

• 初始current_product设为1：因为第一个节点需要乘以1才能得到自身的值，比如根节点值为5，1*5=5，符合路径乘积的定义。
• 用-∞初始化max_product：如果所有路径的乘积都是负数，我们需要选出最大的那个负数（比如-3比-5大），用负无穷才能正确捕获这种情况。
• 叶子节点判断：只有当左右子节点都为空时，才算是一条完整的根到叶子路径，此时才需要更新最大乘积。

迭代版伪代码（用栈模拟DFS） #

如果担心递归深度过大导致栈溢出，可以用迭代版的DFS，用栈来保存遍历状态：

function maxPathProduct(root):
    if root is null:
        return 0
    
    max_product = -∞
    // 栈中存储元组：(当前节点, 当前路径乘积)
    stack = [(root, 1)]
    
    while stack is not empty:
        node, current_product = stack.pop()
        
        // 更新当前路径乘积
        current_product = current_product * node.value
        
        // 到达叶子节点，更新最大乘积
        if node.left is null and node.right is null:
            if current_product > max_product:
                max_product = current_product
            continue
        
        // 栈是后进先出，所以先压右子树，再压左子树，保证遍历顺序和递归一致
        if node.right is not null:
            stack.append( (node.right, current_product) )
        if node.left is not null:
            stack.append( (node.left, current_product) )
    
    return max_product

关键注意事项 #

1. 负数处理：比如路径[-2, -4]的乘积是8，比路径[-2, 3]的-6大，算法会正确选择8。
2. 零的处理：如果某条路径乘积为0，而其他路径都是负数，零会成为最大乘积，算法能正确捕获。
3. 单节点树：如果树只有一个根节点（同时是叶子），算法会返回该节点的值，逻辑正确。
4. 空树情况：根据题目要求调整返回值，比如返回0或者null。

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