LeetCode 687. Longest Univalue Path 最长同值路径 (C++/Java)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode 687. Longest Univalue Path 最长同值路径 (C++/Java)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2270字，纯文字阅读大概需要4分钟。

内容图文

题目：

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.

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.

分析：

给定一颗二叉树，求最长的路径，其中路径是相同节点间的边数。

递归求解此问题，对于每一个结点，我们要求此时最大的路径数，而最大路径数是由其左右两个孩子结点决定的，那么递归的终止条件就是当为空结点时，路径数为0，当我们知道左右孩子的最大路径数时，需要判断当前和左右孩子结点是否相同，如果相同则当前的结点的最大路径数应该为左孩子路径数+1/右孩子路径数+1取最大值，同时更新结果为当前结果和以当前结点根结点时的左右孩子路径数的和的最大值。

程序：

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int longestUnivaluePath(TreeNode* root) {
        int res = 0;
        if(root == nullptr)
            return res;
        univaluePath(root, res);
        return res;
    }
private:
    int univaluePath(TreeNode* root, int& res){
        if(root == nullptr)
            return 0;
        int l = univaluePath(root->left, res);
        int r = univaluePath(root->right, res);
        int pl = 0;
        int pr = 0;
        if(root->left != nullptr && root->val == root->left->val)
            pl = l + 1;
        if(root->right != nullptr && root->val == root->right->val)
            pr = r + 1;
        res = max(res, pl + pr);
        return max(pl, pr);
    }
};

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int longestUnivaluePath(TreeNode root) {
        if(root == null)
            return res;
        univaluePath(root);
        return res;
    }
    private int res = 0;
    private int univaluePath(TreeNode root){
        if(root == null)
            return 0;
        int l = univaluePath(root.left);
        int r = univaluePath(root.right);
        int pl = 0;
        int pr = 0;
        if(root.left != null && root.val == root.left.val)
            pl = l + 1;
        if(root.right != null && root.val == root.right.val)
            pr = r + 1;
        res = Math.max(res, pl + pr);
        return Math.max(pl, pr);
    }
    
}

内容总结

以上是互联网集市为您收集整理的LeetCode 687. Longest Univalue Path 最长同值路径 (C++/Java)全部内容，希望文章能够帮你解决LeetCode 687. Longest Univalue Path 最长同值路径 (C++/Java)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端