687 Longest Univalue Path

687. Longest Univalue Path

1. 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.

2. Implementation

(1) DFS

思路: 先用递归地方法分别得到Left children和Right children的longest univalue path, 然后判断当前的node value是否和left children或者right children的相同，如果是的话，之前得到的longest univalue path加1， 然后与当前得到的最长的univalue path比较

class Solution {
    public int longestUnivaluePath(TreeNode root) {
        int[] res = new int[1];
        getLongestUnivaluePath(root, res);
        return res[0];
    }

    public int getLongestUnivaluePath(TreeNode node, int[] res) {
        if (node == null) {
            return 0;
        }

        int leftPath = getLongestUnivaluePath(node.left, res);
        int rightPath = getLongestUnivaluePath(node.right, res);
        int leftPathFromNode = 0, rightPathFromNode = 0;

        if (node.left != null && node.left.val == node.val) {
            leftPathFromNode = leftPath + 1;
        }

        if (node.right != null && node.right.val == node.val) {
            rightPathFromNode = rightPath + 1;
        }

        res[0] = Math.max(res[0], leftPathFromNode + rightPathFromNode);
        return Math.max(leftPathFromNode, rightPathFromNode);
    }
}

3. Time & Space Complexity

DFS: 时间复杂度: O(n), 空间复杂度: O(h)