时间戳

首页 > 解决方案 > 给定根节点和目标节点的二叉树的总和是多少？

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

问题描述

我有一个二叉树作为函数输入我有树根和 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，但语言并不重要，除非我理解我只想获得最佳解决方案的语法。是否可以提供一些伪代码？

标签： javaalgorithmbinary-tree

解决方案

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

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

推荐阅读