Longest Univalue Path

https://leetcode.com/problems/longest-univalue-path/description/

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.

Thoughts

这道题和Diameter of Binary Tree很像，分为两种大情况: maxLen已经在左右树和该结点与左右结点的path形成新的maxPath。因此我们需要记录对应的两个值。

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
   int len = 0; // global variable
    public int longestUnivaluePath(TreeNode root) {
        if (root == null) return 0;
        len = 0;
        getLen(root, root.val);
        return len;
    }

    private int getLen(TreeNode node, int val) {
        if (node == null) return 0;
        int left = getLen(node.left, node.val);
        int right = getLen(node.right, node.val);
        len = Math.max(len, left + right);
        if (val == node.val)  return Math.max(left, right) + 1;

        return 0;
    }
}

Analysis

Errors:

1. passNodeLeft忘了+1

2. 把passNodeLeft和Right加起来当作了穿过该结点的path长度。这样多考虑了子树的一边从而不是一条path了。

分治遍历一次时间复杂度O(n).

Ver.2

更容易想的但有点丑的解法.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int helper(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int left = helper(root.left);
        int right = helper(root.right);

        int tmp = 1 + (root.left != null && root.left.val == root.val ? left : 0) 
            + (root.right != null && root.right.val == root.val ? right : 0);
        max = Math.max(max, Math.max(tmp, Math.max(left, right)));
        return Math.max(1 + (root.left != null && root.left.val == root.val ? left : 0), 
                       1 + (root.right != null && root.right.val == root.val ? right : 0));
    }


    int max = 1;
    public int longestUnivaluePath(TreeNode root) {
        helper(root);
        return max - 1;
    }
}

Ver.3

iterative solution .

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private void pushLeft(Stack<TreeNode> stack, TreeNode node, Stack<int[]> meta) {
        while (node != null) {
            stack.push(node);
            meta.push(new int[]{1, 1});
            node = node.left;
        }
    }

    public int longestUnivaluePath(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Stack<TreeNode> stack = new Stack<>();
        Stack<int[]> meta = new Stack<>();
        pushLeft(stack, root, meta);
        int max = 0;
        TreeNode pre = null;
        int[] preRes = new int[2];
        while (!stack.isEmpty()) {
            TreeNode node = stack.peek();
            int[] m = meta.peek();
            m[0] = Math.max(m[0], pre != null && pre.val == node.val ? m[0] + preRes[1] : 1);
            m[1] = Math.max(m[1], pre != null && pre.val == node.val ? 1 + preRes[1] : 1);
            if (node.right != null && node.right != pre) {
                pushLeft(stack, node.right, meta);
                preRes = new int[2];
                continue;
            }
            pre = stack.pop();
            preRes = meta.pop();
            max = Math.max(max, m[0]);
        }
        return max - 1;
    }
}