Longest Univalue Path

Question

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.

Solution

這題自己想起來有點亂，雖然大方向沒錯，但 recursion 怎麼設計感覺自己還不是非常清楚。第一次寫有 10 幾個 test case 過不了，嘗試了兩三種方法但都無法 AC，最後看解答。我覺得該注意的有幾個地方：

1. 用這種分治的 recursion，永遠只考慮 root, root.left, root.right 之間的關係。要讓思路切得乾淨，才能寫出正確的 recursion
2. 這題用 global variable 去記錄最大長度，而 recursion 不是 return 最大長度，只 return left or right path 的最大值
3. recursion 中間宣告新的 local variable，是因為要處理 root.left.val != root.val or root.right.val != root.val 的情況

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

    public int helper(TreeNode t) {
        if (t == null) {
            return 0;
        }

        int left = helper(t.left);
        int right = helper(t.right);
        int arrowLeft = 0, arrowRight = 0;
        if (t.left != null && t.val == t.left.val) {
            arrowLeft += left + 1;
        }

        if (t.right != null && t.val == t.right.val) {
            arrowRight += right + 1;
        }

        res = Math.max(res, arrowLeft + arrowRight);
        return Math.max(arrowLeft, arrowRight);
    }