• 解题:根节点到叶子节点所有路径数字之和[难度中]

    2015/09/30 JSRGFJZ 2 评论

题目:

对于一给定树,计算所有路径,从树根节点到叶子节点数字之和

示例:

例如:
1
/\
2 3
其中1个路径为 1->2代表数字 12.,最终返回结果12+13=25.

思路:

两种方法:

>1、

sumHelper(TreeNode *root,int sum),

首先判断本节点是否为空,为空直接返回0,接着开始计算,注意,这里的sum是指从根节点到此节点的上一个节点的sum之和

再者就是判断两个孩子是否都为空

所以最后的函数递归调用sumHelper(root->left,sum)+sumHelper(root->right,sum);

>2、

深搜。

首先判断是否到左右孩子均没有的情况,sum是一个全局变量,此时,我先搜索到最深节点,注意递归内容:10*num+root->left->val

这就是本条路径的所有行进到此节点的sum和,然后我再判断是否左右节点存在,继续用sum分别加上左杰节点内容,而不会改变值大小。

 

代码:

 

 

 

 

 

1 收藏


直接登录
最新评论
  • Clark Li 软件工程师 2015/09/30

    dfs

  • 1w   2015/10/02

    思路:基于遍历树的算法,当进入一个节点时,把此节点对应的数字放到一个栈里面。如果这个节点为叶子,那么此时栈里面的数位代表的数字就用来累加;否则就继续遍历子节点。当从这个节点离开时,把此节点对应的数字从栈里面移除。
    附上代码,请大家指正:)

    代码:
    class Node(object):
    def __init__(self, num, children=None):
    self.num = num
    self.children = children

    def calc(node, digits=None, calculated=0):
    digits = digits or []
    digits.append(node.num) # 把对应的数字放入栈
    if node.children:
    for c in node.children:
    calculated = calc(c, digits, calculated) # 遍历子节点
    else:
    num = _get_num(digits) # 如果为叶子,获取路径上的节点代表的数字
    calculated += num # 累加到结果
    digits.pop() # 离开节点前把数字从栈里取出
    return calculated

    def _get_num(cache):
    t = ”.join([str(i) for i in cache])
    return int(t)

    if __name__ == ‘__main__’:
    node9 = Node(9)
    node8 = Node(8)
    node4 = Node(4, [node8, node9])
    node5 = Node(5)
    node6 = Node(6)
    node7 = Node(7)
    node2 = Node(2, [node4, node5, node6])
    node3 = Node(3, [node7])
    root = Node(1, [node2, node3])

    print(calc(root))