LeetCode 687. Longest Univalue Path

[Woodyiiiiiii]

Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root.

The length of path between two nodes is represented by the number of edges between them.

Example 1:

Input:

              5
             / \
            4   5
           / \   \
          1   1   5

Output: 2

Example 2:

Input:

              1
             / \
            4   5
           / \   \
          4   4   5

Note: The given binary tree has not more than 10000 nodes. The height of the tree is not more than 1000.

---

这道题做过类似的，跟124. binary-tree-maximum-path-sum很相似。

首先判断是先序遍历还是后序遍历(DFS+树形遍历)，因为路径不一定经过根节点，所以采用后者。接下来，我们要判断节点内的值“相等”的问题，我一开始的思路是从左右子节点中选取值跟当前节点的值比对，然而这很复杂，更简便的是因为树形DFS是先递归再回溯的过程，我们不能只关注“回溯”这一部分，可以从 “递归” 部分下手，即把当前节点的值跟父亲节点的值进行比对。

然后，考虑函数返回的问题，按照题目要求我们返回的是路径值，从左右递归结果中取出最大的路径值再加一，最后返回。最后，将路径结果值声明为属性，在函数中选择左右路径和和自身的最大值。

class Solution {
    int res = 0;
    public int longestUnivaluePath(TreeNode root) {
        process(root, 0);
        return res;
    }
    public int process(TreeNode node, int preVal) {
        if (node == null) return 0;
        int left = process(node.left, node.val);
        int right = process(node.right, node.val);
        res = Math.max(res, left + right);
        if (node.val == preVal) {
            return Math.max(left, right) + 1;
        }else {
            return 0;
        }
    }
}

---

相似题目：

• https://leetcode.com/problems/binary-tree-maximum-path-sum/

参考资料：

• https://leetcode.com/problems/longest-univalue-path/
• https://leetcode.com/problems/longest-univalue-path/discuss/674655/JAVA-straightforward-recursive-solution-2ms-faster-than-97