计算二叉树中节点之间的最大差异

Question

有没有办法在不存储在列表中的情况下计算节点值之间的最大差异？我希望一次性完成，但似乎不可能。这是来自一个 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)

Answer 1

如果您想知道从根到叶的任何路径上两个节点之间的最大差异，您可以使用以下代码：

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))

它将跟踪每条路径上的最小值和最大值。一旦它到达叶子，它就会简单地 return 这两者之间的差异，从而停止递归。对于 non-leaf 个节点，它将首先更新最小值和最大值。然后它递归到 children 和 return 两个结果之间的最大值。

计算二叉树中节点之间的最大差异

Calculate the max difference between nodes in a binary tree

python

binary-tree

amplitude