网络异常，图片无法展示
|
「这是我参与2022首次更文挑战的第16天，活动详情查看：2022首次更文挑战」
给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
注意：两个节点之间的路径长度由它们之间的边数表示。
示例 1:
输入:
5 / \ 4 5 / \ \ 1 1 5 复制代码
输出:
2 复制代码
示例 2:
输入:
1 / \ 4 5 / \ \ 4 4 5 复制代码
输出:
2 复制代码
注意: 给定的二叉树不超过10000个结点。 树的高度不超过1000。
解题思路
本题就是一个裸的递归题。
求最长的同值路径，可以通过求得所有的同值路径，然后找到其中的最大值得到。那如何获取所有的同值路径呢？
我们观察二叉树可以发现，每一条路径都有一个顶点，我们以每一个节点为顶点获取同值路径，也就获取到了所有的同值路径。
所以我们可以通过递归输入的二叉树，求得以每一个节点为顶点的同值路径。那如何求得同值路径呢？
首先在向下递归的过程中，我们需要记录当前节点的父节点值，以供回溯过程使用。
在回溯过程中，假设我们已经拿到了当前节点的同值路径的长度，此时如果父节点的值和当前节点的值相同，那么父节点和当前节点可以组成同值路径，我们应该把当前节点的同值路径的值 +1 作为返回值。+1 是因为父节点值和当前节点值相同，则它们之间的边属于同值路径的一条边。
如果父节点的值和当前节点值不同，则它们不能组成同值路径，此时返回 0。
当前节点为顶点的同值路径的长度，就是其左子树的返回值加上其右子树的返回值，每次拿到当前节点为顶点的同值路径长度，尝试用该长度更新结果值，这样回溯完成，就获取到了二叉树中的最长同值路径。
代码实现
var longestUnivaluePath = function(root) { // 初始化结果值为 0 let max = 0; // 递归函数，求以每一个节点为顶点的同值路径的长度 function findPath(node){ // 递归函数退出条件，如果节点为 null，返回 0 if(node === null) return 0; // 向下递归的过程中记录当前节点的父节点的值，以便的回溯的过程中使用 if(node.left) node.left.parentVal = node.val if(node.right) node.right.parentVal = node.val // 获取左子树的返回值 const l = findPath(node.left), // 获取右子树的返回值 r = findPath(node.right) // 尝试用当前节点为顶点获取到的同值路径的长度更新结果值 max = Math.max(max,l+r) // 如果有父节点节点值和当前节点是否相同 // 如果相同，返回左右子树返回值的最大值 +1 if(node.parentVal===node.val) return Math.max(l,r)+1 // 如果不同，返回 0 return 0; } // 调用方法 findPath(root) // 返回结果值 return max; }; 复制代码
至此我们就完成了 leetcode-687-最长同值路径
如有任何问题或建议，欢迎留言讨论！👏🏻👏🏻👏🏻
