Welcome to Subscribe On Youtube
  • /**
    
     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);
            }
        }
    }
    
    ############
    
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        private int ans;
    
        public int longestUnivaluePath(TreeNode root) {
            ans = 0;
            dfs(root);
            return ans;
        }
    
        private int dfs(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int left = dfs(root.left);
            int right = dfs(root.right);
            left = root.left != null && root.left.val == root.val ? left + 1 : 0;
            right = root.right != null && root.right.val == root.val ? right + 1 : 0;
            ans = Math.max(ans, left + right);
            return Math.max(left, right);
        }
    }
    
  • // 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:
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right
    class Solution:
        def longestUnivaluePath(self, root: TreeNode) -> int:
            def dfs(root):
                if root is None:
                    return 0
                left, right = dfs(root.left), dfs(root.right)
                left = left + 1 if root.left and root.left.val == root.val else 0
                right = right + 1 if root.right and root.right.val == root.val else 0
                nonlocal ans
                ans = max(ans, left + right)
                return max(left, right)
    
            ans = 0
            dfs(root)
            return ans
    
    ############
    
    # 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]
    
  • /**
     * Definition for a binary tree node.
     * type TreeNode struct {
     *     Val int
     *     Left *TreeNode
     *     Right *TreeNode
     * }
     */
    func longestUnivaluePath(root *TreeNode) int {
    	ans := 0
    	var dfs func(root *TreeNode) int
    	dfs = func(root *TreeNode) int {
    		if root == nil {
    			return 0
    		}
    		left, right := dfs(root.Left), dfs(root.Right)
    		if root.Left != nil && root.Left.Val == root.Val {
    			left++
    		} else {
    			left = 0
    		}
    		if root.Right != nil && root.Right.Val == root.Val {
    			right++
    		} else {
    			right = 0
    		}
    		ans = max(ans, left+right)
    		return max(left, right)
    	}
    	dfs(root)
    	return ans
    }
    
    func max(a, b int) int {
    	if a > b {
    		return a
    	}
    	return b
    }
    
  • /**
     * Definition for a binary tree node.
     * class TreeNode {
     *     val: number
     *     left: TreeNode | null
     *     right: TreeNode | null
     *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
     *         this.val = (val===undefined ? 0 : val)
     *         this.left = (left===undefined ? null : left)
     *         this.right = (right===undefined ? null : right)
     *     }
     * }
     */
    
    function longestUnivaluePath(root: TreeNode | null): number {
        if (root == null) {
            return 0;
        }
    
        let res = 0;
        const dfs = (root: TreeNode | null, target: number) => {
            if (root == null) {
                return 0;
            }
    
            const { val, left, right } = root;
    
            let l = dfs(left, val);
            let r = dfs(right, val);
            res = Math.max(res, l + r);
            if (val === target) {
                return Math.max(l, r) + 1;
            }
            return 0;
        };
        dfs(root, root.val);
        return res;
    }
    
    
  • /**
     * Definition for a binary tree node.
     * function TreeNode(val, left, right) {
     *     this.val = (val===undefined ? 0 : val)
     *     this.left = (left===undefined ? null : left)
     *     this.right = (right===undefined ? null : right)
     * }
     */
    /**
     * @param {TreeNode} root
     * @return {number}
     */
    var longestUnivaluePath = function (root) {
        let ans = 0;
        let dfs = function (root) {
            if (!root) {
                return 0;
            }
            let left = dfs(root.left),
                right = dfs(root.right);
            left = root.left?.val == root.val ? left + 1 : 0;
            right = root.right?.val == root.val ? right + 1 : 0;
            ans = Math.max(ans, left + right);
            return Math.max(left, right);
        };
        dfs(root);
        return ans;
    };
    
    
  • // Definition for a binary tree node.
    // #[derive(Debug, PartialEq, Eq)]
    // pub struct TreeNode {
    //   pub val: i32,
    //   pub left: Option<Rc<RefCell<TreeNode>>>,
    //   pub right: Option<Rc<RefCell<TreeNode>>>,
    // }
    //
    // impl TreeNode {
    //   #[inline]
    //   pub fn new(val: i32) -> Self {
    //     TreeNode {
    //       val,
    //       left: None,
    //       right: None
    //     }
    //   }
    // }
    use std::rc::Rc;
    use std::cell::RefCell;
    impl Solution {
        fn dfs(root: &Option<Rc<RefCell<TreeNode>>>, target: i32, res: &mut i32) -> i32 {
            if root.is_none() {
                return 0;
            }
    
            let root = root.as_ref().unwrap().as_ref().borrow();
            let left = Self::dfs(&root.left, root.val, res);
            let right = Self::dfs(&root.right, root.val, res);
            *res = (*res).max(left + right);
            if root.val == target {
                return left.max(right) + 1;
            }
            0
        }
    
        pub fn longest_univalue_path(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
            if root.is_none() {
                return 0;
            }
    
            let mut res = 0;
            Self::dfs(
                &root,
                root.as_ref().unwrap().as_ref().borrow().val,
                &mut res,
            );
            res
        }
    }
    
    
  • /**
     * 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);
        }
    }
    
    ############
    
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        private int ans;
    
        public int longestUnivaluePath(TreeNode root) {
            ans = 0;
            dfs(root);
            return ans;
        }
    
        private int dfs(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int left = dfs(root.left);
            int right = dfs(root.right);
            left = root.left != null && root.left.val == root.val ? left + 1 : 0;
            right = root.right != null && root.right.val == root.val ? right + 1 : 0;
            ans = Math.max(ans, left + right);
            return Math.max(left, right);
        }
    }
    
  • // 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:
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right
    class Solution:
        def longestUnivaluePath(self, root: TreeNode) -> int:
            def dfs(root):
                if root is None:
                    return 0
                left, right = dfs(root.left), dfs(root.right)
                left = left + 1 if root.left and root.left.val == root.val else 0
                right = right + 1 if root.right and root.right.val == root.val else 0
                nonlocal ans
                ans = max(ans, left + right)
                return max(left, right)
    
            ans = 0
            dfs(root)
            return ans
    
    ############
    
    # 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]
    
  • /**
     * Definition for a binary tree node.
     * type TreeNode struct {
     *     Val int
     *     Left *TreeNode
     *     Right *TreeNode
     * }
     */
    func longestUnivaluePath(root *TreeNode) int {
    	ans := 0
    	var dfs func(root *TreeNode) int
    	dfs = func(root *TreeNode) int {
    		if root == nil {
    			return 0
    		}
    		left, right := dfs(root.Left), dfs(root.Right)
    		if root.Left != nil && root.Left.Val == root.Val {
    			left++
    		} else {
    			left = 0
    		}
    		if root.Right != nil && root.Right.Val == root.Val {
    			right++
    		} else {
    			right = 0
    		}
    		ans = max(ans, left+right)
    		return max(left, right)
    	}
    	dfs(root)
    	return ans
    }
    
    func max(a, b int) int {
    	if a > b {
    		return a
    	}
    	return b
    }
    
  • /**
     * Definition for a binary tree node.
     * class TreeNode {
     *     val: number
     *     left: TreeNode | null
     *     right: TreeNode | null
     *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
     *         this.val = (val===undefined ? 0 : val)
     *         this.left = (left===undefined ? null : left)
     *         this.right = (right===undefined ? null : right)
     *     }
     * }
     */
    
    function longestUnivaluePath(root: TreeNode | null): number {
        if (root == null) {
            return 0;
        }
    
        let res = 0;
        const dfs = (root: TreeNode | null, target: number) => {
            if (root == null) {
                return 0;
            }
    
            const { val, left, right } = root;
    
            let l = dfs(left, val);
            let r = dfs(right, val);
            res = Math.max(res, l + r);
            if (val === target) {
                return Math.max(l, r) + 1;
            }
            return 0;
        };
        dfs(root, root.val);
        return res;
    }
    
    
  • /**
     * Definition for a binary tree node.
     * function TreeNode(val, left, right) {
     *     this.val = (val===undefined ? 0 : val)
     *     this.left = (left===undefined ? null : left)
     *     this.right = (right===undefined ? null : right)
     * }
     */
    /**
     * @param {TreeNode} root
     * @return {number}
     */
    var longestUnivaluePath = function (root) {
        let ans = 0;
        let dfs = function (root) {
            if (!root) {
                return 0;
            }
            let left = dfs(root.left),
                right = dfs(root.right);
            left = root.left?.val == root.val ? left + 1 : 0;
            right = root.right?.val == root.val ? right + 1 : 0;
            ans = Math.max(ans, left + right);
            return Math.max(left, right);
        };
        dfs(root);
        return ans;
    };
    
    
  • // Definition for a binary tree node.
    // #[derive(Debug, PartialEq, Eq)]
    // pub struct TreeNode {
    //   pub val: i32,
    //   pub left: Option<Rc<RefCell<TreeNode>>>,
    //   pub right: Option<Rc<RefCell<TreeNode>>>,
    // }
    //
    // impl TreeNode {
    //   #[inline]
    //   pub fn new(val: i32) -> Self {
    //     TreeNode {
    //       val,
    //       left: None,
    //       right: None
    //     }
    //   }
    // }
    use std::rc::Rc;
    use std::cell::RefCell;
    impl Solution {
        fn dfs(root: &Option<Rc<RefCell<TreeNode>>>, target: i32, res: &mut i32) -> i32 {
            if root.is_none() {
                return 0;
            }
    
            let root = root.as_ref().unwrap().as_ref().borrow();
            let left = Self::dfs(&root.left, root.val, res);
            let right = Self::dfs(&root.right, root.val, res);
            *res = (*res).max(left + right);
            if root.val == target {
                return left.max(right) + 1;
            }
            0
        }
    
        pub fn longest_univalue_path(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
            if root.is_none() {
                return 0;
            }
    
            let mut res = 0;
            Self::dfs(
                &root,
                root.as_ref().unwrap().as_ref().borrow().val,
                &mut res,
            );
            res
        }
    }
    
    

All Problems

All Solutions