数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会研究
时尚研究
法律研究Python程序在树的两个节点间寻找最长路径
假设我们有一棵二叉树；我们必须找到树中任意两个节点之间最长的路径。
所以，如果输入像
那么输出将是5
为了解决这个问题，我们将遵循以下步骤
ans := 0
定义函数getMaxPath()。它将占用节点
如果节点为null，则
返回0
leftCnt := getMaxPath(节点的左节点)
rightCnt := getMaxPath(节点的右节点)
temp := 1 + leftCnt和rightCnt的最大值
ans := ans和l+r+1的最大值
在main方法中执行以下操作 −
getMaxPath(root)
返回ans
让我们看看以下实现，以获得更好的理解 −
示例
class TreeNode: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right class Solution: def solve(self, root): self.ans = 0 def getMaxPath(root): if root is None: return 0 l = getMaxPath(root.left) r = getMaxPath(root.right) temp = max(l, r) + 1 self.ans = max(self.ans, l + r + 1) return temp getMaxPath(root) return self.ans ob = Solution() root = TreeNode(2) root.left = TreeNode(10) root.right = TreeNode(4) root.right.left = TreeNode(8) root.right.right = TreeNode(2) root.right.left.left = TreeNode(6) print(ob.solve(root))
输入
root = TreeNode(2) root.left = TreeNode(10) root.right = TreeNode(4) root.right.left = TreeNode(8) root.right.right = TreeNode(2) root.right.left.left = TreeNode(6)
输出
5
更新时间：10-10-2020
851次浏览
广告