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

用 Python 编写程序，计算二叉树中每个对角线路径元素的总和

pythonserver side programmingprogramming更新于 2026/1/12 13:00:17

假设我们有一棵二叉树，我们必须从上到下计算树中每个对角线的总和。

因此，如果输入如下

那么输出将是 [27, 18, 3]，因为对角线是 [12,15]、[8,10]、[3]。因此总和值为 [27, 18, 3]

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

定义一个函数 traverse() 。这将获取节点、numLeft、输出

  • 如果节点为空，则

    • 返回

  • 如果 numLeft >= 输出大小，则

    • 在输出末尾插入节点数据

  • 否则，

    • output[numLeft] := output[numLeft] + 节点数据

  • 如果节点左侧不为空，则

    • traverse(节点左侧、numLeft+1， output)

  • 如果节点的右侧不为空，则

    • traverse(节点的右侧，numLeft，输出)

  • 从主方法中，执行以下操作 −

  • output := 新列表

  • traverse(根，0，output)

  • 返回output

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

示例

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):
      output = []
      def traverse(node, numLeft, output):
         if not node:
            return
         if numLeft >= len(output):
            output.append(node.data)
         else:
            output[numLeft] += node.data
         if node.left:
            traverse(node.left, numLeft+1, output)
         if node.right:
            traverse(node.right, numLeft, output)
      traverse(root, 0, output)
      return output
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))

输入

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

输出

[27, 18, 3]

相关文章

有用资源

打印 下一节:用 Python 编写程序按排序顺序查找给定数字的所有素因数 ❯❮ 上一节:用 Python 编写程序检查字符串的两个部分是否为回文