素材牛VIP会员
一道算法题,用python初始化一颗二叉树并求解其最短路径的值
 ji***ui  分类:Python  人气:1371  回帖:7  发布于4年前 收藏

题目:
一颗二叉树,每个节点都有自己的值,在二叉树上找到一条路径(根节点到某个叶子节点之间的路线就是路径)上所有节点的值要最小,输出最小的值是多少!这里的最短路径不是按跳数来,而是按节点值的和来,不要搞错了!

示例:
一行的开头如果输入为0,表示结束输入,空节点用null表示

输入:
    5
2       3
0

输出:
7

输入:
                          1
            2                        18
    3             5            null       2
100    1    null    8               null    null
0

输出:
7(1+2+3+1)

应该是用递归解,有懂的朋友能帮忙解答下嘛?

 标签:算法python

讨论这个帖子(7)垃圾回帖将一律封号处理……

Lv1 新人
飘***子 JS工程师 4年前#1

我觉得是简单dp(瞎说的

Lv2 入门
13***22 JAVA开发工程师 4年前#2
def minPathSum(node):
    if not node:
        return 0
    return min(minPathSum(node.left), minPathSum(node.right)) + node.val
Lv6 码匠
阿***灯 页面重构设计 4年前#3

leetcode上有类似的,不过只是求跳数的题目:https://leetcode.com/problems/minimum-depth-of-binary-tree/

这是我的python实现,你稍微改一下就行

class Solution(object):
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
       
        if root is None:
            return 0
        if root.left is None:
            return 1 + self.minDepth(root.right)
        if root.right is None:
            return 1 + self.minDepth(root.left)
        return 1 + min(self.minDepth(root.left), self.minDepth(root.right))
Lv5 码农
蜗***牛 Linux系统工程师 4年前#4

应该是树形DP吧

Lv6 码匠
小***6 JS工程师 4年前#5

java写的,楼主看看

https://github.com/terry83299387/MyTest/blob/master/BinaryTreeMinSum.java

Lv5 码农
wz***16 技术总监 4年前#6

动态规划中的入门问题。

Lv6 码匠
街***铃 JS工程师 4年前#7

用php试了下,可以看看https://github.com/chianquan/Mytest/blob/master/shortest.php

 文明上网,理性发言!   😉 阿里云幸运券,戳我领取