HTML CSS JAVASCRIPT JQUERY AI PHP SQL EXCEL LINUX C# C++ C PYTHON JAVA 教程库 参考手册 技术文章 测验 练习 HOWTO FAQ

用 Python 编写程序，在二叉树上查找 k 长度路径

pythonserver side programmingprogramming更新于 2026/1/12 2:20:17

假设我们有一个包含唯一值的二叉树，并且我们还有另一个值 k，我们必须找到树中 k 长度唯一路径的数量。路径可以从父节点到子节点，也可以从子节点到父节点。当某个节点出现在一条路径中，而另一条路径中没有出现时，我们将认为两条路径是不同的。

因此，如果输入如下

k = 3，则输出将为 4，因为路径为 [12,8,3]、[12,8,10]、[8,12,15]、[3,8,10]。

为了解决这个问题，我们将遵循以下步骤−

  • 定义一个函数 dfs() 。这将获取节点

    • 如果节点为空，则

      • 返回一个包含 1 和 k-1 个 0 的列表

    • left := dfs(节点左侧)

    • right := dfs(节点右侧)

    • 对于 0 到 K 范围内的 i，执行

      • ans := ans + left[i] * right[K - 1 - i]

    • res := 一个大小为 K 的 0 列表

    • res[0] := 1, res[1] := 1

    • 对于范围从 1 到 K - 1 的 i，执行

      • res[i + 1] := res[i + 1] + left[i]

      • res[i + 1] := res[i + 1] + right[i]

    • 返回 res

  • 从 main 方法，执行下列操作−

  • ans := 0


  • dfs(root)


  • 返回 ans


让我们看看下面的实现以便更好地理解 −

示例

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
class Solution:
   def solve(self, root, K):
      def dfs(node):
         if not node:
            return [1] + [0] * (K-1)
         left = dfs(node.left)
         right = dfs(node.right)
         for i in range(K):
            self.ans += left[i] * right[K - 1 - i]
         res = [0] * K
         res[0] = res[1] = 1
         for i in range(1, K - 1):
            res[i + 1] += left[i]
            res[i + 1] += right[i]
         return res
      self.ans = 0
      dfs(root)
      return self.ans
ob = Solution()
root = TreeNode(12)
root.left = TreeNode(8)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(10)
print(ob.solve(root, 3))

输入

root = TreeNode(12)
root.left = TreeNode(8)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(10)
3

输出

4

相关文章

有用资源

打印 下一节:用 Python 检查新旧版本编号是否正确的程序 ❯❮ 上一节:用 Python 编写程序计算包含奇数位的列表中元素的数量