LeetCode.687.Longest Univalue Path 二叉树的最长同值路径

题目描述

687 Longest Univalue Path
https://leetcode-cn.com/problems/longest-univalue-path/

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
Output: 2

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

---

相似题目

LeetCode.687.Longest Univalue Path 二叉树的最长同值路径
LeetCode.543.Diameter of Binary Tree 二叉树的直径
LeetCode.124.Binary Tree Maximum Path Sum 二叉树的最大路径和

---

解题过程

递归计算深度，过程中更新全局变量，不同之处在于：
递归函数 depth 返回的是和根节点 root 同值的路径长度
如果root节点与左子树/右子树的值一样，长度才加一
root 与左、右子树值一样时，链接左右同值深度，形成经过root点的路径，并考虑更新全局变量。

时间复杂度 O(n)，空间复杂度 O(n)

private static class SolutionV2020 {
    private int length;
    public int longestUnivaluePath(TreeNode root) {
        if (null == root) {
            return 0;
        }
        length = 0;
        depth(root);
        return length;
    }

    // 返回和根节点root同值的路径深度
    private int depth(TreeNode root) {
        if (null == root) {
            return 0;
        }
        // 左右子树中和跟同值的高度
        int left = 0, right = 0;
        if (null != root.left) {
            int d = depth(root.left);
            left = root.left.val == root.val ? d + 1 : 0;
        }
        if (null != root.right) {
            int d = depth(root.right);
            right = root.right.val == root.val ? d + 1 : 0;
        }
        // 更新最长同值路径
        length = Math.max(length, left + right);
        return Math.max(left, right);
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_687_LongestUnivaluePath.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_687_LongestUnivaluePath.java

---