687. 最长同值路径

approach 1，后序遍历

class Solution {
    int res = 0;
    public int longestUnivaluePath(TreeNode root) {
        return Math.max(recursive(root), res);
    }

    // max length
    private int recursive(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int left = recursive(root.left);
        int right = recursive(root.right);

        if (root.left != null && root.right != null && root.left.val == root.right.val && root.val == root.left.val) {
            res = Math.max(res, left + right + 2);
        }

        int max = 0;
        if (root.left != null && root.left.val == root.val) {
            max = left + 1;
        }

        if (root.right != null && root.right.val == root.val) {
            max = Math.max(max, right + 1);
        }

        res = Math.max(res, max);
        return max;
    }
}

优化后

class Solution {
    int ans = 0;
    public int longestUnivaluePath(TreeNode root) {
        dfs(root);
        return ans;
    }

    private int dfs(TreeNode n) {
        if (n == null) return 0;

        int l = dfs(n.left);
        int r = dfs(n.right);
        int ll = 0, rr = 0;
        if (n.left != null && n.val == n.left.val) {
            ll = l + 1;
        }

        if (n.right != null && n.val == n.right.val) {
            rr = r + 1;
        }
        
        ans = Math.max(ans, ll + rr);
        return Math.max(ll, rr);
    }
}