Leetcode(687) Longest Univalue Path

发表于 | 更新于 | 分类于

Description:

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. Note: 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.

解法：

这道题让我们求最长的相同值路径，对于这种树的路径问题，递归是不二之选。在递归函数中，我们首先对其左右子结点调用递归函数，得到其左右子树的最大相同值路径，下面就要来看当前结点和其左右子结点之间的关系了，如果其左子结点存在且和当前节点值相同，则left自增1，否则left重置0；同理，如果其右子结点存在且和当前节点值相同，则right自增1，否则right重置0。然后用left+right来更新结果res。而调用当前节点值的函数只能返回left和right中的较大值，因为如果还要跟父节点组path，就只能在左右子节点中选一条path，当然选值大的那个了，具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    int res;

    public int longestUnivaluePath(TreeNode root) {
        res = 0;
        helper(root);
        return res;
    }

    public int helper(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 0;
        }
        int left = helper(root.left);
        int right = helper(root.right);
        if (root.left != null && root.val == root.left.val) {
            left++;
        } else {
            left = 0;
        }
        if (root.right != null && root.val == root.right.val) {
            right++;
        } else {
            right = 0;
        }
        if (left + right > res) {
            res = left + right;
        }
        if (left > right) {
            return left;
        }
        return right;
    }
}