Erlang 中的二叉树最大路径

Question

Binary Tree Maximum Path问题可以通过使用DFS来解决。这是在 Python.

中使用此方法的可能 solution

def maxPathSum(self, root):
    def maxSum(root):
        if not root:
            return 0
        l_sum = maxSum(root.left)
        r_sum = maxSum(root.right)
        l = max(0, l_sum)
        r = max(0, r_sum)
        res[0] = max(res[0], root.val + l + r)
        return root.val + max(l, r)
    
    res = [-float('inf')]
    maxSum(root)
    return res[0]

我正尝试在 Erlang 中使用相同的方法。假设 node 看起来像：

{Value, Left, Right}

我想到了：

max_sum(undefined) -> 0;
max_sum({Value, Left, Right}) ->
    LeftSum = max(0, max_sum(Left)),
    RightSum = max(0, max_sum(Right)),
    %% Where to store the max? Should I use the process dictionary?
    %% Should I send a message?
    Value + max(LeftSum, RightSum).

max_path_sum(Root) ->
  %% Bonus question: how to represent -infinity in Erlang?
  max_sum(Root)

Erlang 中没有全局变量。如何在 DFS 期间跟踪最大值？我唯一想到的是使用流程字典或 ETS table 或者可能有一个可以保持最大值的不同流程，但也许我想多了，有更简单和惯用的方法吗？

Answer 1

最“erlangish”的方法是将全局最大值作为第二个参数传递，return它与局部最大值一起传递：

max_sum(undefined, GlobalMax) -> {0, GlobalMax};
max_sum({Value, Left, Right}, GlobalMax0) ->
    {LeftSum, GlobalMax1} = max(0, max_sum(Left, GlobalMax0)),
    {RightSum, GlobalMax2} = max(0, max_sum(Right, GlobalMax1)),
    NewGlobalMax =
        case GlobalMax2 of
            undefined ->
                Value + LeftSum + RightSum
            _ ->
                max(GlobalMax2, Value + LeftSum + RightSum)
        end,
    {Value + max(LeftSum, RightSum), NewGlobalMax}.

max_path_sum(Root) ->
    {_, GlobalMax} = max_sum(Root, undefined),
    GlobalMax.

Erlang ，所以我用原子 undefined 来表示最小值。

Erlang 中的二叉树最大路径

Binary Tree Maximum Path in Erlang

erlang