公司做网站需要准备什么东西,广告网站制作报价,网站建设解决方案ppt,西安网站建设公司西安网络公司题目不长#xff0c;就是分析时间太久了。
思路使用dfs深度遍历#xff0c;先想好这个函数返回什么#xff0c;题目给出路径可以是子-父-子的路径#xff0c;那么1-2-3可以#xff0c;3-2-1也可以#xff0c;那么考虑dfs返回两个值#xff0c;对于当前节点node来说就是分析时间太久了。
思路使用dfs深度遍历先想好这个函数返回什么题目给出路径可以是子-父-子的路径那么1-2-3可以3-2-1也可以那么考虑dfs返回两个值对于当前节点node来说返回一个顺序的长度的最大值p一个逆序长度的最大值b初始值都为1。例如当前节点值为3下面有两个子节点1-2那么p为3b仍为1。
这是返回的值那么对于当前节点以node为终点的最大长度max(p,b)还有一种经过node节点的路径需要考虑例如左节点为1右节点为3当前节点为2。
这题需要把所有的情况罗列一遍就是多几个if语句
class Solution:def __init__(self):self.m 1def longestConsecutive(self, root: Optional[TreeNode]) - int:self.dfs(root)return self.mdef dfs(self, node):if not node: return 0, 0p, b, m 1, 1, 1p1, b1 self.dfs(node.left)p2, b2 self.dfs(node.right)if node.left and abs(node.left.val - node.val) 1:if node.left.val - node.val -1:p max(p, p1 1)else:b max(b, b1 1)if node.right and abs(node.right.val - node.val) 1:if node.right.val - node.val -1:p max(p, p2 1)else:b max(b, b2 1)if node.left and node.right and node.left.val - node.val node.val - node.right.val:if node.left.val - node.val -1:m b2 p1 1elif node.left.val - node.val 1:m b1 p2 1self.m max(self.m, p, b, m)return p, b
