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

爱被打了一巴掌 2022-05-13 15:58 180阅读 0赞

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

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

**示例 1:**

输入:

5
                 / \
                4   5
               / \   \
              1   1   5

输出:

**示例 2:**

输入:

1
                 / \
                4   5
               / \   \
              4   4   5

输出:

**注意:** 给定的二叉树不超过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