最长同值路径

题目

题目来源：力扣（LeetCode）

给你一个整数数组 nums，请你将该数组升序排列。

给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
注意：两个节点之间的路径长度由它们之间的边数表示。

示例 1:

输入:

          5<br />             / \<br />            4   5<br />           / \   \<br />          1   1   5<br />输出:<br />2

示例 2:

输入:

          1<br />             / \<br />            4   5<br />           / \   \<br />          4   4   5<br />输出:<br />2

思路分析

路径长度 = 节点数 - 1

根据上述公式，要求出符合要求的路劲，就需要先求出二叉树中具有相同值的所有节点。

对于二叉树本身就具有递归这种性质的数据结构，我们需要把它看成“左子树-根节点-右子树”这种结构，就不要再囿于左子节点／右子节点这个思维里了。这道题其实可以看成是解决以root为路径起始点的最长路径，这其实就只有两种情况：
(1) 第一种是root和左子树（同值），如图中以4为路径起始点：root->lef

(2) 第二种是root和右子树（同值），如图中以4为路径起始点：root->right

(3) 还有一种特殊情况，那就是左子树-root-右子树（同值）

/**
 * 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}
 */
// 返回以 root 节点为起点的最长同值路径
// 该路径要么是以 root 为起点的左子树: root -> left ; 要么是以 root 为起点的右子树: root -> right
var longestUnivaluePath = function (root) {
    let res = 0
    const dfs = (root) => {
        if (root == null) {
            return 0
        }
        const left = dfs(root.left) // root左子树的最长同值路径
        const right = dfs(root.right) // root右子树的最长同值路径
        let leftPath = 0, rightPath = 0
         // 从左右子树中选择最长的同值路径
        if (root.left && root.left.val == root.val) {
            leftPath = left + 1
        }
        if (root.right && root.right.val == root.val) {
            rightPath = right + 1
        }
        // 左子树 + 根 + 右子树 形成一条同值路径
        res = Math.max(res, leftPath + rightPath) // 记录全局
        return Math.max(rightPath, leftPath)
    }
    dfs(root)
    // 返回最长路径值
    return res
}