Tree Algorithm:Branch Sum

1435-郭同学

发表文章数:18

热门标签

, , ,
首页 » 算法 » 正文

算法刷题系列 Algorithm


Difficulty:easy

Branch Sum

Write a function that takes in a Binary Tree and returns a list of its branch sums ordered from leftmost branch sum to rightmost branch sum.
A branch sum is the sum of all values in a Binary Tree branch. A Binary Tree branch is a path of nodes in a tree that starts at the root node and ends at any leaf node.
Each BinaryTree node has an integer value , a left child node, and a right child node. Children nodes can either be BinaryTree nodes themselves or None / null .
Tree Algorithm:Branch Sum
Solution :
O(N) time | O(N) space
We are returning a list of branch sums that has the length as the number of branches.
There are roughly half of N leaf in the Binary tree, which is 1/2 N.

class BinaryTree:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


def branchSums(root):
	sums = []
	calculateBranchsum(root, 0, sums)
	return sums

def calculateBranchsum(node, runningsum, sums):
	if node is None:
		return
	newrunningsum = runningsum + node.value
	if node.left is None and node.right is None:
		sums.append(newrunningsum)
		return
	
	calculateBranchsum(node.left, newrunningsum, sums)
	calculateBranchsum(node.right, newrunningsum, sums)

from AlgoExpert

未经允许不得转载:作者:1435-郭同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《Tree Algorithm:Branch Sum》 发布于2021-02-20

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录