687. Longest Univalue 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
class Solution {
    private static class Holder {
        private int maxPathLength;
    }

    public int longestUnivaluePath(TreeNode root) {
        Holder holder = new Holder();

        dfs(root, holder);

        return holder.maxPathLength;
    }

    private int dfs(TreeNode root, Holder holder) {
        if (root == null) {
            return 0;
        }

        // 自底向上
        int leftMaxPathLength = dfs(root.left, holder);
        int rightMaxPathLength = dfs(root.right, holder);

        int leftGain = 0, rightGain = 0; // 此处保证节点连续，即 root 值与子节点不同则不会累加左子树或右子树的路径长度
        if (root.left != null && root.left.val == root.val) {
            leftGain = leftMaxPathLength + 1;
        }
        if (root.right != null && root.right.val == root.val) {
            rightGain = rightMaxPathLength + 1;
        }

        holder.maxPathLength = Math.max(holder.maxPathLength, leftGain + rightGain);
        return Math.max(leftGain, rightGain);
    }
}

References

687. Longest Univalue Path