看网站不受限制的浏览器_东莞乐从网站建设_整站优化工具_天津关键词排名推广

题目：687. 最长同值路径

难度：中等

给定一个二叉树的 root ，返回 最长的路径的长度 ，这个路径中的 每个节点具有相同值 。 这条路径可以经过也可以不经过根节点。

两个节点之间的路径长度 由它们之间的边数表示。

示例 1:

输入：root = [5,4,5,1,1,5]
输出：2

示例 2:

输入：root = [1,4,5,4,4,5]
输出：2

提示:

• 树的节点数的范围是 [0, 104] 
• -1000 <= Node.val <= 1000
• 树的深度将不超过 1000 

一、模式识别

路径可能穿过父节点 》 后序

同值 》 任意同值（不一定和根节点相同） 》 全局比较 + 同值条件判断

二、代码实现

1.递归

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:if not root: return 0ans = 0def dfs(node):if not node: return 0left = dfs(node.left)right = dfs(node.right)left = left + 1 if node.left and node.val == node.left.val else 0right= right + 1 if node.right and node.val == node.right.val else 0nonlocal ansans = max(ans, left + right)return max(left, right)dfs(root)return ans

2.迭代

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:if not root: return 0ans = 0stack = [root]records = defaultdict(int)while stack:node = stack.pop()if node:stack.append(node)stack.append(None)if node.right: stack.append(node.right)if node.left: stack.append(node.left)else:node = stack.pop()left = records[node.left] + 1 if node.left and node.left.val == node.val else 0right = records[node.right] + 1 if node.right and node.right.val == node.val else 0ans = max(ans, left + right)records[node] = max(left, right)return ans