leetcode

687-最长同值路径

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

示例 1:

1
2
3
4
5
6
7
8
输入:
              5          
             / \      
            4   5
           / \   \   
          1   1   5 
输出:
2

示例 2:

1
2
3
4
5
6
7
8
输入:
              1
             / \     
            4   5   
           / \   \  
          4   4   5 
输出:
2

注意:

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

解答

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
class Solution {
    public int longestUnivaluePath(TreeNode root) {
        if (root == null)
            return 0;
        int res = help(root.left, root.val) + help(root.right, root.val);
        int left = longestUnivaluePath(root.left);
        int right = longestUnivaluePath(root.right);
        int max = res > left ? res : left;  // 注4
        max = max > right ? max : right;  // 注4
        return max;

    }

    public int help(TreeNode root, int parent) {
        if (root == null)
            return 0;
        int res = 0;
        if (root.val == parent)  // 注1
            res += 1;
        else
            return 0;  // 注3
        int left = help(root.left, parent);
        int right = help(root.right, parent);
        res += left > right ? left : right; // 注2
        return res;
    }

}

其他

这道题咋一看没思路,后面发现例题中三个节点相等时结果为2,也就是两条连接线.

  • 注1.而且节点的父节点值跟自己相等时,连接数应该+1.
  • 注2.这个路径同一个节点不能分叉,所以只能取其中一条分支的连接数累加上来.
  • 注3.并且为了保证是相连的,如果遇到和父节点值不一样的,直接return.
  • 注4.遍历所有节点,取最大值