687. Longest Univalue Path - Easy
发布时间:2020-12-14 05:17:59 所属栏目:大数据 来源:网络整理
导读: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 betwee
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. ? time: O(n),space: O(height) /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { int length = 0; public int longestUnivaluePath(TreeNode root) { if(root == null) { return 0; } helper(root); return length; } public int helper(TreeNode root) { if(root == null) { return 0; } int l = helper(root.left); int r = helper(root.right); int left = 0,right = 0; if(root.left != null && root.val == root.left.val) { left = l + 1; } if(root.right != null && root.val == root.right.val) { right = r + 1; } length = Math.max(length,left + right); return Math.max(left,right); } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |