本文共 2313 字，大约阅读时间需要 7 分钟。

领扣LintCode算法问题答案-1085. 最长的单一路径

1085. 最长的单一路径

描述

给定一颗二叉树，找到路径中每个节点具有相同值的最长路径的长度。 此路径可能会也可能不会通过根节点。

1. 两个节点之间的路径长度由它们之间的边数表示。
2. 给定的二叉树不超过10000个节点。 树的高度不超过1000。

样例 1：

输入:              5             / \            4   5           / \   \          1   1   5输出:2

样例 2：

输入:              1             / \            4   5           / \   \          4   4   5输出:2

题解

/** * Definition of TreeNode: * public class TreeNode { *     public int val; *     public TreeNode left, right; *     public TreeNode(int val) { *         this.val = val; *         this.left = this.right = null; *     } * } */public class Solution {
       /**     * @param root:      * @return: the length of the longest path where each node in the path has the same value     */    public int longestUnivaluePath(TreeNode root) {
           // Write your code here        Pointer
   
     maxValue = new Pointer<>(0);        longestUnivaluePath(root, maxValue);        return maxValue.v;    }        private int longestUnivaluePath(TreeNode root, Pointer
    
      maxValue) {
           if (root == null            || (root.left == null && root.right == null)) {
               return 0;        }        int leftCount = longestUnivaluePath(root.left, maxValue);        int rightCount = longestUnivaluePath(root.right, maxValue);        if (root.left != null            && root.left.val == root.val) {
               leftCount = leftCount + 1;        } else {
               leftCount = 0;        }        if (root.right != null            && root.right.val == root.val) {
               rightCount = rightCount + 1;        } else {
               rightCount = 0;        }        int rootCount = 0;        if (root.left != null                && root.right != null) {
               rootCount = leftCount + rightCount;        }        maxValue.v = max(maxValue.v, leftCount, rightCount, rootCount);        return max(leftCount, rightCount);    }    private int max(int...nums) {
           int ret = nums[0];        for (int num : nums) {
               if (num > ret) {
                   ret = num;            }        }        return ret;    }    class Pointer
     
       {
           private T v;        public Pointer(T v) {
               this.v = v;        }    }}
     
    
   

鸣谢

非常感谢你愿意花时间阅读本文章，本人水平有限，如果有什么说的不对的地方，请指正。

欢迎各位留言讨论，希望小伙伴们都能每天进步一点点。

转载地址：https://le-yi.blog.csdn.net/article/details/108809405 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！