687. Longest Univalue Path

题目描述和难度

  • 题目描述：

给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。

注意：两个节点之间的路径长度由它们之间的边数表示。

示例 1:

输入:

              5
             / \
            4   5
           / \   \
          1   1   5

输出:

2

示例 2:

输入:

              1
             / \
            4   5
           / \   \
          4   4   5

输出:

2

注意: 给定的二叉树不超过10000个结点。 树的高度不超过1000。

思路分析

求解关键：

参考解答

参考解答1

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

/**
 * 687. 最长同值路径
 * https://leetcode-cn.com/problems/longest-univalue-path/description/
 *
 * @author liwei
 */
public class Solution {

    public int longestUnivaluePath(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int[] res = new int[1];
        longestUnivaluePath(root, res);
        return res[0];
    }

    /**
     * 途径 node 的相同结点的最长路径
     *
     * @param node
     * @param res
     * @return
     */
    private int longestUnivaluePath(TreeNode node, int[] res) {
        if (node == null) {
            return 0;
        }
        int l = longestUnivaluePath(node.left, res);
        int r = longestUnivaluePath(node.right, res);
        int pl = 0;
        int pr = 0;
        if (node.left != null && node.val == node.left.val) {
            pl = l + 1;
        }
        if (node.right != null && node.val == node.right.val) {
            pr = r + 1;
        }
        // 这一步很关键，这一步在更新全局的 answer
        res[0] = Math.max(res[0], pl + pr);
        // 返回只能使用单边最长的额路径
        return Math.max(pl, pr);
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0687-longest-univalue-path ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。