"原文链接 [链接] Description: 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 th .."

[每日 LeetCode] 687. Longest Univalue Path

原文链接 [每日 LeetCode] 687. Longest Univalue Path

Description:

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.


思路:本题要求二叉树中相等结点的最长路径。考虑借助 DFS,在进行递归的同时增加记录路径的变量,并及时更新最长路径。


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)
            dfs(root, res);
        return res;
    }
    
    int dfs(TreeNode* root, int& res){
        int l = root->left ? dfs(root->left, res) : 0;
        int r = root->right ? dfs(root->right, res) : 0;
        
        int leftEdge = (root->left && root->left->val == root->val) ? l + 1 : 0;
        int rightEdge = (root->right && root->right->val == root->val) ? r + 1 : 0;
        res = max(res, leftEdge + rightEdge);
        return max(leftEdge, rightEdge);
    }
};

运行时间:124ms

运行内存:50M

  • LeetCode

    LeetCode(力扣)是一个全球极客挚爱的高质量技术成长平台,想要学习和提升专业能力从这里开始,充足技术干货等你来啃,轻松拿下 Dream Offer!

    151 引用 • 35 回帖
  • Tree
    33 引用 • 5 回帖
  • Easy
    101 引用 • 10 回帖
回帖   
请输入回帖内容...