如何找到二叉树中任意两个节点之间的最大差异

Question

有谁能帮助我理解下面的算法，如何找出二叉树中任意两个节点之间的最大差异。

http://www.geeksforgeeks.org/maximum-difference-between-node-and-its-ancestor-in-binary-tree/

我不明白为什么他们试图从左子树和右子树得到最小值，而实际上我们想要最大的差异

提前谢谢！！

Answer 1

和往常一样，有几种方法可以实现这一点，而你的方法可能和Geeksforgeks提出的方法一样有效，尽管对我来说这似乎更难实现。

当前节点和任何其他节点之间的最大差异是通过将当前子树的最小值从当前值减去来获得的。这就是为什么他们要取右子树和左子树的最小值。到目前为止的最大差异包含在ref指针中，如果需要，它会更新。

Answer 2

为了找到最大的差异，从最小值中减去最大值就足够了。您提供的链接描述了一个不同问题的算法：找到最大差异|A-B|，其中A是B的祖先。