leetcode [687] 最长同值路径

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

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

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

示例 1:

输入:

              5
             / \
            4   5
           / \   \
          1   1   5
输出:

2

示例 2:

输入:

              1
             / \
            4   5
           / \   \
          4   4   5
输出:

2

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

class Solution:
    def longestUnivaluePath(self, root: TreeNode) -> int:
        if root is None:
            return 0
        maxval = 0

        def helper(root):
            if root is None:
                return 0
            nonlocal maxval
            left_arrow, right_arrow = 0, 0
            left = helper(root.left)
            right = helper(root.right)
            if root.left and root.left.val == root.val:
                left_arrow = left + 1
            if root.right and root.right.val == root.val:
                right_arrow = right + 1
            maxval = max(maxval, left_arrow + right_arrow)
            return max(left_arrow, right_arrow)
        helper(root)
        return maxval

class Solution:
    def longestUnivaluePath(self, root: TreeNode) -> int:
        if root is None:
            return 0
        current, maxval = self.longestUnivaluePathCore(root)
        return max(current, maxval)

    def longestUnivaluePathCore(self, root: TreeNode) -> int:
        if root is None:
            return [0, 0]
        left_arrow, right_arrow = 0, 0
        left_current, left_max = self.longestUnivaluePathCore(root.left)
        right_current, right_max = self.longestUnivaluePathCore(root.right)
        if root.left and root.left.val == root.val:
            left_arrow = left_current + 1
        if root.right and root.right.val == root.val:
            right_arrow = right_current + 1
        maxval = max(left_arrow + right_arrow, left_max, right_max)
        return (max(left_arrow, right_arrow), maxval)