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 } }