leetcode 687. 最长同值路径(python)

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

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

示例 1:

输入:

5 / \ 4 5 / \ \ 1 1 5

输出:

2

示例 2:

输入:

1 / \ 4 5 / \ \ 4 4 5

输出:

2

注意: 给定的二叉树不超过10000个结点。 树的高度不超过1000。

---

解题思路： 如果当前节点值不和父节点相同，则返回0；若相同，则返回左右子树中边数较多的一个，加1是因为当他与父节点的值相同时，和父节点还有一个连线。maxLen用来动态记录边数最多的路径。

# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): maxLen = 0 def longestUnivaluePath(self, root): """ :type root: TreeNode :rtype: int """ if not root: return 0 self.getMaxLen(root, root.val) return self.maxLen def getMaxLen(self, root, val): if not root: return 0 left = self.getMaxLen(root.left, root.val) right = self.getMaxLen(root.right, root.val) self.maxLen = max(self.maxLen, left + right) if root.val == val: return max(left, right) + 1 return 0