687 Longest Univalue Path
687. Longest Univalue Path
题目: https://leetcode.com/problems/longest-univalue-path/
难度:
Easy
思路
这道题也只能算个easy题目，根据传进来的root，我们只要从它的左右节点不停的递归下去，只要其value值与root一样，
该方向上的length就加1，最后我们将左右方向上的length相加, 递归取最大值
很重要的一点就是，Note: The length of path between two nodes is represented by the number of edges between them.
- 因此是
self.res = max(self.res, left_arrow + right_arrow),return max(left_arrow, right_arrow) - 而不是
self.res = max(self.res, left_arrow + right_arrow + 1),return max(left_arrow + 1, right_arrow + 1)
# 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):
def longestUnivaluePath(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.res = 0
def dir_length(node):
if not node:
return 0
left_len = dir_length(node.left) # 左节点的length
right_len = dir_length(node.right) # 右节点的length
left_dir, right_dir = 0, 0
if node.left and node.left.val == node.val:
left_dir = left_len + 1 # 当前节点的左节点方向的length
if node.right and node.right.val == node.val:
right_dir = right_len + 1 # 当前节点的右边节点方向的length
self.res = max(self.res, left_dir + right_dir)
return max(left_dir, right_dir)
dir_length(root)
return self.res
