Approach: DFS returning longest same-value arm; bend at each node

def longestUnivaluePath(self, root):
    self.best = 0
    def dfs(node):
        if not node: return 0
        l = dfs(node.left); r = dfs(node.right)
        lp = l + 1 if node.left and node.left.val == node.val else 0
        rp = r + 1 if node.right and node.right.val == node.val else 0
        self.best = max(self.best, lp + rp)
        return max(lp, rp)
    dfs(root)
    return self.best

Complexity: O(n) time, O(h) space.

Full Solution — all languages

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def longestUnivaluePath(self, root):
        self.best = 0
        def dfs(node):
            if not node: return 0
            l = dfs(node.left); r = dfs(node.right)
            lp = l + 1 if node.left and node.left.val == node.val else 0
            rp = r + 1 if node.right and node.right.val == node.val else 0
            self.best = max(self.best, lp + rp)
            return max(lp, rp)
        dfs(root)
        return self.best

import java.util.*;
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int v) {
        val = v;
    }
}
class Solution {
    public int longestUnivaluePath(TreeNode root) {
        best = 0;
        dfs(root);
        return best;
    }
    int best;
    private int dfs(TreeNode node) {
        if (node == null) return 0;
        int l = dfs(node.left), r = dfs(node.right);
        int lp = (node.left != null && node.left.val == node.val) ? l + 1 : 0;
        int rp = (node.right != null && node.right.val == node.val) ? r + 1 : 0;
        best = Math.max(best, lp + rp);
        return Math.max(lp, rp);
    }
}

#include <bits/stdc++.h> using namespace std;
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v): val(v), left(nullptr), right(nullptr) {
    }
};
class Solution {
    public: int longestUnivaluePath(TreeNode* root) {
        int best = 0;
        function<int(TreeNode*)> dfs = [&](TreeNode* node) -> int {
            if (!node) return 0;
            int l = dfs(node->left), r = dfs(node->right);
            int lp = (node->left && node->left->val == node->val) ? l + 1 : 0;
            int rp = (node->right && node->right->val == node->val) ? r + 1 : 0;
            best = max(best, lp + rp);
            return max(lp, rp);
        };
        dfs(root);
        return best;
    }
};

/**
 * Tree node shape: { val, left, right }
 * @param {TreeNode} root
 * @return {number}
 */ var longestUnivaluePath = function(root) {
    let best = 0;
    const dfs = (node) => {
        if (!node) return 0;
        const l = dfs(node.left), r = dfs(node.right);
        const lp = (node.left && node.left.val === node.val) ? l + 1 : 0;
        const rp = (node.right && node.right.val === node.val) ? r + 1 : 0;
        best = Math.max(best, lp + rp);
        return Math.max(lp, rp);
    };
    dfs(root);
    return best;
};

Longest Univalue Path

Example 1

Example 2

Constraints