Java

  • /**
    
     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.
    
     */
    
    public class Longest_Univalue_Path {
        /**
         * Definition for a binary tree node.
         * public class TreeNode {
         *     int val;
         *     TreeNode left;
         *     TreeNode right;
         *     TreeNode(int x) { val = x; }
         * }
         */
        class Solution {
    
            int longest = 0;
    
            public int longestUnivaluePath(TreeNode root) {
    
                if (root == null) {
                    return 0;
                }
    
                dfs(root);
    
                return longest;
            }
    
            private int dfs(TreeNode root) {
    
                if (root == null) {
                    return 0;
                }
    
                int leftLeaf = dfs(root.left);
                int rightLeaf = dfs(root.right);
    
                int leftCount = 0;
                int rightCount = 0;
    
                if (root.left != null && root.left.val == root.val) {
                    leftCount = 1 + leftLeaf;
                }
                if (root.right != null && root.right.val == root.val) {
                    rightCount = 1 + rightLeaf;
                }
    
                int total = leftCount + rightCount; // here is edge, not node count
                longest = Math.max(longest, total);
    
                return Math.max(leftCount, rightCount);
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/longest-univalue-path/
    // Time: O(N)
    // Space: O(H)
    class Solution {
        int ans = 0;
        int dfs(TreeNode *root) {
            if (!root) return 0;
            int left = dfs(root->left), right = dfs(root->right);
            if (!root->left || root->left->val != root->val) left = 0;
            if (!root->right || root->right->val != root->val) right = 0;
            ans = max(ans, 1 + left + right);
            return 1 + max(left, right);
        }
    public:
        int longestUnivaluePath(TreeNode* root) {
            dfs(root);
            return max(0, ans - 1);
        }
    };
    
  • # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def longestUnivaluePath(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            longest = [0]
            def dfs(root):
                if not root:
                    return 0
                left_len, right_len = dfs(root.left), dfs(root.right)
                left = left_len + 1 if root.left and root.left.val == root.val else 0
                right = right_len + 1 if root.right and root.right.val == root.val else 0
                longest[0] = max(longest[0], left + right)
                return max(left, right)
            dfs(root)
            return longest[0]
    

Java

  • /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        int ans;
    
        public int longestUnivaluePath(TreeNode root) {
            ans = 0;
            arrowLength(root);
            return ans;
        }
    
        public int arrowLength(TreeNode node) {
            if (node == null)
                return 0;
            int left = arrowLength(node.left);
            int right = arrowLength(node.right);
            int arrowLeft = 0, arrowRight = 0;
            if (node.left != null && node.left.val == node.val)
                arrowLeft += left + 1;
            if (node.right != null && node.right.val == node.val)
                arrowRight += right + 1;
            ans = Math.max(ans, arrowLeft + arrowRight);
            return Math.max(arrowLeft, arrowRight);
        }
    }
    
  • // OJ: https://leetcode.com/problems/longest-univalue-path/
    // Time: O(N)
    // Space: O(H)
    class Solution {
        int ans = 0;
        int dfs(TreeNode *root) {
            if (!root) return 0;
            int left = dfs(root->left), right = dfs(root->right);
            if (!root->left || root->left->val != root->val) left = 0;
            if (!root->right || root->right->val != root->val) right = 0;
            ans = max(ans, 1 + left + right);
            return 1 + max(left, right);
        }
    public:
        int longestUnivaluePath(TreeNode* root) {
            dfs(root);
            return max(0, ans - 1);
        }
    };
    
  • # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def longestUnivaluePath(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            longest = [0]
            def dfs(root):
                if not root:
                    return 0
                left_len, right_len = dfs(root.left), dfs(root.right)
                left = left_len + 1 if root.left and root.left.val == root.val else 0
                right = right_len + 1 if root.right and root.right.val == root.val else 0
                longest[0] = max(longest[0], left + right)
                return max(left, right)
            dfs(root)
            return longest[0]
    

All Problems

All Solutions