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.

Example 1:

Input:

              5
             / \
            4   5
           / \   \
          1   1   5

Output:

2

Example 2:

Input:

              1
             / \
            4   5
           / \   \
          4   4   5

Output:

2

Note: The given binary tree has not more than 10000 nodes. The height of the tree is not more than 1000.

Solution:

  • Method 1: Divide and conquer(Recursion). ```Java /**
    • Definition for a binary tree node.
    • public class TreeNode {
    • int val;
    • TreeNode left;
    • TreeNode right;
    • TreeNode(int x) { val = x; }
    • } */ class Solution { private int result; public int longestUnivaluePath(TreeNode root) { if(root == null) return 0; getPath(root); return this.result - 1; } private int getPath(TreeNode node){ if(node == null) return 0; int left = getPath(node.left); int right = getPath(node.right); int res = 1 + ((node.left == null || node.left.val == node.val) ? left: 0) + ((node.right == null || node.right.val == node.val) ? right: 0); this.result = Math.max(result, res); return Math.max((node.left == null || node.left.val == node.val) ? left: 0, (node.right == null || node.right.val == node.val) ? right: 0) + 1; } } ```