2

リストに保存せずにノード値間の最大差を計算する方法はありますか? 1回でやりたいと思っていたのですが、無理そうです。これは、ノードの最大絶対差として定義されるバイナリ ツリーの振幅を計算するための codility インタビューの質問からのものです。

        def max_diff(nodes):
            return abs(max(nodes) - min(nodes))

        def amplitude(T):
            nodes = []
            def calc_amplitude(T, nodes):

                if not isinstance(T, tuple):
                    if not isinstance(T, int):
                        return 0
                    nodes.append(T)
                    return T
                else:
                    [calc_amplitude(t, nodes) for t in T]
                    return max_diff(nodes)
            return calc_amplitude(T, nodes)

        tree = (5, (8, (12, None, None), (2, None, None)),(9, (7, (1, None, None), None), (4, (3, None, None), None)))

        print amplitude(tree)
4

1 に答える 1

3

ルートからリーフへの任意のパス上の 2 つのノード間の最大差を知りたい場合は、次のコードを使用できます。

def amplitude(tree, cur_min=None, cur_max=None):
    if tree is None:
        if cur_min is None:
            return 0
        else:
            return cur_max - cur_min

    if cur_min is None:
        cur_min = cur_max = tree[0]
    else:
        cur_min = min(cur_min, tree[0])
        cur_max = max(cur_max, tree[0])

    return max(amplitude(tree[1], cur_min, cur_max),
               amplitude(tree[2], cur_min, cur_max))

各パスの最小値と最大値を追跡します。リーフに到達すると、単純にこれら 2 つの差が返されるため、再帰が停止します。非リーフ ノードの場合、最初に最小値と最大値が更新されます。次に、両方の子に再帰し、2 つの結果の間の最大値を返します。

于 2016-05-08T11:51:14.577 に答える