LeetCode687最长同值路径

Posted on | | Visitors:
Words count in article: 489 字 | Reading time ≈ 2 分

题目链接

https://leetcode-cn.com/problems/longest-univalue-path/

题解

  • 这道题写了好久，然后参考了题解
  • 递归解法
  • 这道题和LeetCode543二叉树的直径(点击查看)非常相似，可以看一下
  • 类似的题目还有LeetCode124(点击查看)，非常相似，难度是Hard
  • 将一条路径分为左右两半，两个结点之间路径长度等于它们到根结点的距离之和
  • 思路见代码注释，关键的代码是26-29行
  • 需要高度注意dfs函数的功能
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// Problem: LeetCode 687
// URL: https://leetcode-cn.com/problems/longest-univalue-path/
// Tags: Tree Recursion DFS
// Difficulty: Easy

#include <iostream>
#include <algorithm>
using namespace std;

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
};

class Solution{
private:
    int maxLen = 0;  // 全局最长同值路径

    // 功能：返回该树与根结点同值的路径（必须以根结点为起点，至多经过一个子树）的最大长度
    int dfs(TreeNode* root){
        // 空树则长度为0
        if (root == nullptr)
            return 0;
        // 该树根结点在左右方向上的最长同值路径的长度（从根结点开始，路径上的结点的值都与根结点一致）
        int left = dfs(root->left);
        int right = dfs(root->right);
        left = (root->left != nullptr && root->val == root->left->val) ? left + 1 : 0;
        right = (root->right != nullptr && root->val == root->right->val) ? right + 1 : 0;
        // 更新全局最长同值路径
        maxLen = max(maxLen, left + right); // 将一条路径分为左右两半，两个结点之间路径长度等于它们到根结点的距离之和
        // 经过左子树或者右子树，或者不经过子树（left和right都为0时）
        return max(left, right);
    }

public:
    // 求该树中的最长同值路径，可以经过也可以不经过根结点
    int longestUnivaluePath(TreeNode* root) {
        dfs(root);
        return this->maxLen;
    }
};

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!