python解决求二叉树的最长同值路径问题
给定一颗二叉树，在其中寻找一条最长路径的问题，在这条路径上的所有节点都具有相同的值。值得注意的是这条最长路径可能经过根也可能不经过根，在计算两个节点之间的距离时我们通常会用它们所代表的意义来衡量距离大小如上所示这是一颗典型的二叉树结构
添加图片注释，不超过 140 字（可选）
添加图片注释，不超过 140 字（可选）
给定的两颗二叉树的最长同值路径输出都为2。
给定问题中的最长同值路径，在试图用函数求解整个二叉树时会面临较高的难度。然而，在处理单个节点时思路则相对明确。因此我们可以将这一复杂的问题拆分为多个较小规模的子问题，并自然采用递归策略进行解决。例如以下所示的二叉树结构可以帮助我们具体阐述递归函数的操作流程
添加图片注释，不超过 140 字（可选）
添加图片注释，不超过 140 字（可选）
如上图所示，在执行递归函数A的过程中，从调用A(5)到最终返回所求最长同值路径数值的过程如下：首先将函数A(5)压入栈中，在根节点5处其左子节点为4，则将函数A(4)也压入栈中；接着在节点4处再次调用其左子节点1而压入函数A(1)；在节点1处再次调用左子节点为空的情况而压入函数A(null)；当处理完所有空树结构后（即函数A(null)），其返回值为零并依次向上返回给父层处理：即返回值零对应于上层调用函数A(1)时处理left分支的结果；此时进入right分支处理阶段：即执行right=self.A(root.right)，此时同样将函数A(null)压入栈中并完成计算过程。
添加图片注释，不超过 140 字（可选）
返回值为0的是A(1)函数中的right变量初始化为0，在这种情况下该函数能够执行return max(left,right)的操作并将结果传递给上层的0位置随后该函数将退出栈框
添加图片注释，不超过 140 字（可选）
返回值为0，在该函数体中左侧赋值为0。其中，在处理右侧子树时（即在处理root.right），执行右侧子树的操作。其中，在处理右侧子树时（即在处理root.right），其右子树为空，则执行进栈操作
添加图片注释，不超过 140 字（可选）
然后返回位置为right=0的是A(4)函数体内的变量初始化值，在此情况下A(4)函数将执行计算left与right的最大值并将其结果通过return语句传递给调用者所在的位置，并立即退出当前函数体以完成程序流程控制
添加图片注释，不超过 140 字（可选）
使用python的代码实现如下：
class Solution(object):
def main(self, root): #主函数main
self.max_length=0 #全局变量，用于保存当前最长同值路径
self.A(root)
return self.max_length
def A(self,root): #被调函数，也是递归函数
if not root:
return 0
left=self.A(root.left)
right=self.A(root.right)
if root.left and root.left.val==root.val:
left+=1
else:
left=0
if root.right and root.right.val==root.val:
right+=1
else:
right=0
self.max_length=max(self.max_length,left+right)
return max(left,right) #返回给上层的是左右子路径最长同值路径