java - 给定根节点和目标节点的二叉树之和是多少？

Question

我有一个二叉树 作为函数输入，我有树根和 2 个节点 我需要沿着两个给定节点之间的路径计算总和。

一棵树的例子:

     4
   /   \
  8    13
 / \
24 45

代码:

List<Node> findPath(root, target):
if (root !=null)
    return
if root == node{
    return nodes.add(target)
}
path = findPath(root.left, target)
if (path !=null){
    return nodes.add(root).addAll(path)
}
path = findPath(root.right, target)
if (path!=null)
      return nodes.add(root).addAll(path)

如果我有目标节点的路径，我不知道下一步是什么，我应该如何计算最佳路径？

Input: sumTree(4, 24, 45)
Output: 8 + 24 + 45 = 77

Input: sumTree(4, 24, 13)
Output: 13 + 4 + 8 + 24 = 49

Input: sumTree(4, 4, 13)
Output: 4 + 13 = 17

Input: sumTree(4, 45, 45)
Output: 45

语言是JAVA，但语言并不重要，除非我理解语法 我只想有最佳解决方案。 是否可以提供一些伪代码？

Answer 1

您的两个路径将具有相同的前缀(至少根应该在那里)。 您需要删除公共(public)前缀并仅添加最后一个(最深的)公共(public)节点(一次)。对于不同的部分，您需要添加所有值。这应该是 O(N) 复杂度，并且与解决方案的其余部分一致。

您的搜索算法效率不高，因为您不断将值从一个列表复制到另一个列表(O(N^2) 如果您对树没有任何约束)。如果您修改它以就地构建响应，它应该变为 O(N)。