687. Longest Univalue Path

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.

package tree;

import com.google.common.collect.Lists;

import java.util.Random;

/**
 * Created by cqs on 2018/3/18.
 */
public class LongestUnivaluePath {

    private int max = 0;

    public static void main(String[] args) {
        LongestUnivaluePath lp = new LongestUnivaluePath();
        BinaryTree0 bt = new BinaryTree0();
//        Integer[] integers = lp.initArray(10);
//        Integer[] integers = {5, 4, 5, 1, 1, 5};
        Integer[] integers = {26, 26, 26, 26, 26, 24, 26, 25, 25, 25, 27, 23, 25, 25, 27, 24, 26, 24, 26, 24, 24, null, 28, null, null, 26, null, null, 26, 26, 28, 25, null, 25, 27, null, null, null, null, null, 23, null, null, 29, 27, null, null, null, null, 25, null, 27, 27, 24, 26, 24, 26, 26, 26, null, 22, 28, null, 26, 26, null, null, 26, null, 28, 28, 25, null, null, null, 25, 25, 25, 27, 25, 25, 27, 25, null, null, null, null, null, null, null, 27, 27, 27, null, null, 27, 29, 24, 26, 26, 26, null, 26, null, 26, null, null, null, 24, 24, 24, null, 26, 24, 26, null, null, null, 26, null, null, null, 28, null, 30, null, 23, 27, null, null, null, null, null, null, null, null, null, null, null, 23, 25, 25, 25, 27, 25, 23, 25, null, null, null, null, null, null, 29, null, null, null, 26, null, 22, null, null, 26, 24, 26, null, 26, 28, null, null, 26, 22, null, null, null, null, null, null, null, null, null, null, 25, 23, null, null, null, null, 27};
//        System.out.println(Lists.newArrayList(integers));
        TreeNode root = bt.buildTree(integers);
        System.out.println(lp.longestUnivaluePath(root));
    }

    public int longestUnivaluePath(TreeNode root) {
        path(root);
        return max;
    }

    //表示root左边或者右边和node.val相等的路径长度
    private int path(TreeNode node) {
        if (node == null) return 0;
        int left = path(node.left);
        int right = path(node.right);
        if (node.left == null || node.left.val != node.val) left = 0;
        if (node.right == null || node.right.val != node.val) right = 0;
        max = Math.max(max, left + right);
        return Math.max(left, right) + 1;
    }

}

//二叉树
class BinaryTree0 {
    private Random random = new Random();
    private TreeNode root;

    //构建二叉树
    TreeNode buildTree(Integer[] arr) {
        TreeNode[] nodes = new TreeNode[arr.length];
        for (int i = arr.length - 1; i >= 0; --i) {
            nodes[i] = arr[i] == null ? null : new TreeNode(arr[i]);
            if (nodes[i] == null) continue;
            int left = 2 * i + 1;
            nodes[i].left = left > (arr.length - 1) ? null : nodes[left];
            int right = 2 * (i + 1);
            nodes[i].right = right > (arr.length - 1) ? null : nodes[right];
        }
        return root = nodes[0];
    }

    //随机生成数组
    private Integer[] initArray(int size) {
        Integer[] is = new Integer[size];
//
        for (int i = 0; i < is.length; i++) {
            is[i] = random.nextInt(size * 10);

        }
        return is;
    }
}