687. Longest Univalue Path

题干简述：

给我们一个二叉树的根节点，求该二叉树其路径上所有节点值相同的最长路径长度。该路径可以包含根节点。

路径长度为节点间的边的数目。

解题思路

这一题乍一看，不免会有点困惑，因为我们很容易把问题想复杂。题干让我们求解具有相同节点值的最大路径长度，到这里其实都还好，重点在于后面的那句，“该路径可包含根节点，也可不包含”。这个时候，我们就会想很多种情况，比方说根节点和左右子节点都不相等，根节点和左右子节点中某个相等，根节点和左右子节点都相等；又或包含根节点的路径如何与其子树中的最长路径比较呢。想着想着，就会觉得这个问题无从下手。导致这个问题的根源，还是我以前说过的，我们没有一个程序员的角度，来思考这个问题。

首先，作为一个程序员，在提到二叉树时，会想到什么？作为程序员，我们应该清楚的意识到，二叉树是一种天然支持递归的数据结构，二叉树的前中后序遍历，DFS/BFS 都能很好的体现这一点。意识到这一点之后，就让我们顺着这个思路，思考如果利用递归，该如何解决这道题？

递归，作为一种解题思路，其实它也是有模板可依的。无论怎样的递归函数，无外乎以下四点：

  • 输入参数：我们传递什么进去；

  • 输出结果：我们返回什么出来给上一层使用；

  • 函数的功能/目的：这个递归函数是为了解决什么问题；

  • 终止条件：当输入参数满足什么结果时，代表我们已经执行到最底层，需要停止递归并开始逐层返回；

代入到这一题，分别是：

  • 输入参数：node 节点；

  • 输出结果：该 node 节点下最长相同值路径；

  • 函数的功能/目的：计算该 node 节点最长相同值路径；

  • 终止条件：当 node 为 空时，返回；

梳理完主体脉络之后，再让我们来雕琢一下细节之处。先看下官方提供的 3 个 case：

687-1

这里 case 1 和 case 2 都很好理解，重点来看下 case 3；case 3 的实际输出结果为 2，他的结果实际上有 3 种形式：

687-2

其中，适用于普通的递归函数的，是第二种和第三种，因为递归函数必须要有一个输出结果，这也就要求返回的路径，必须包含 node 节点自身，因为它是向上返回的，而node 节点下方是左子树还是右子树，则要看哪边更长了。那第一种我们就可以忽视了吗？自然也不是，第一种其实就是我们上面提到的“其子树中的最长路径”的一种形式，它的结果并不向上返回，但是它的长度还是要统计进来，毕竟，我们求得是最长相同值路径长度。

如果我们将求路径长度封装成为一个递归方法 getPathLen，那么这个方法要做的事就可以抽象为以下几步：

(1) 判断终结条件：if (!node）return 0

(2) 通过 getPathLen 获取 node 左右子树的路径长度 left, right

(3) 更新此时的最大长度，即对应上述情况 1

(4) 返回包含 node 在内的最长路径长度

步骤清晰了，我们要做的就是通过代码实现了。

题解

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var longestUnivaluePath = function(root) {
    let res = 0;
    const getPathLen = (node) => {
        if (!node) return 0; // 递归终结
        const left = getPathLen(node.left);
        const right = getPathLen(node.right);
        let leftDepth = 0;
        let rightDepth = 0;
        if (node.left && node.left.val === node.val) {
            leftDepth = left + 1;
        }
        if (node.right && node.right.val === node.val) {
            rightDepth = right + 1;
        }
        res = Math.max(res, leftDepth + rightDepth);
        return Math.max(leftDepth,rightDepth)
    };
    getPathLen(root);
    return res;
};

为什么这里是 res = Math.max(res, leftDepth + rightDepth); 呢？仔细想想，如果 node.val === node.left.val && node.val === node.right.val，此时，通过 node 的最长路径长度，就应为 getPathLen(node.left) + 1 与 getPathLen(node.right) + 1 之和；而如果有一个值不等，在上面的 if 语句的限制下，对应的 depth 也不会更新，这样相加的时候就能保证结果是正确的。

Q.E.D.

Take it easy