Python程序：查找二叉树中每条对角线路径元素的和

假设我们有一个二叉树，我们需要找到从树的顶部到右下角的每条对角线的元素之和。

因此，如果输入如下所示：

则输出将为 [27, 18, 3]，因为对角线为 [12,15]、[8,10]、[3]。所以和值为 [27, 18, 3]

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

定义一个函数 traverse()。它将接收节点、左侧节点数、输出作为参数。

• 如果节点为空，则

  • 返回。

• 如果左侧节点数大于或等于输出的大小，则

  • 将节点的数据插入到输出的末尾。

• 否则，

  • 输出[左侧节点数] := 输出[左侧节点数] + 节点的数据。

• 如果节点的左子节点不为空，则

  • 遍历(节点的左子节点, 左侧节点数+1, 输出)。

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

  • 遍历(节点的右子节点, 左侧节点数, 输出)。

• 在主方法中，执行以下操作：

• 输出 := 一个新的列表。

• 遍历(根节点, 0, 输出)。

• 返回输出。

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

示例

 在线演示

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]

Arnab Chakraborty

更新于: 2020年10月7日

109 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习