LeetCode 687. 最长同值路径

Category Difficulty Likes Dislikes
algorithms Medium (48.06%) 805 -

Tags

tree | recursion

Companies

google

题目:

给定一个二叉树的 root ，返回最长的路径的长度 ，这个路径中的每个节点具有相同值 。 这条路径可以经过也可以不经过根节点。
两个节点之间的路径长度由它们之间的边数表示。

输入：root = [5,4,5,1,1,5]
输出：2
输入：root = [1,4,5,4,4,5]
输出：2

提示:

  • 树的节点数的范围是 [0, 104]
  • -1000 <= Node.val <= 1000
  • 树的深度将不超过 1000

思路

recursion
递归问题,找最长同值路径.从根节点开始,分别访问左右子树,如果左右子树的值和根节点的值相同,那么路径长度+1,否则置为0.最后返回左右子树的最长同值路径.

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
43
44
45
/*
 * @lc app=leetcode.cn id=687 lang=cpp
 *
 * [687] 最长同值路径
 */
// Definition for a binary tree node.
// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution
{
public:
    int longestPath(TreeNode *root)
    {
        int longest = 0;
        ArrowLength(root, longest);
        return longest;
    }
private:
    int ArrowLength(TreeNode *node, int &longest)
    {
        if (!node)
            return 0;
        int leftLength = ArrowLength(node->left, longest);
        int rightLength = ArrowLength(node->right, longest);
        int left_length = 0, right_length = 0;
        if (node->left && node->left->val == node->val){
            left_length = leftLength + 1;
        }
        if (node->right && node->right->val == node->val){
            right_length = rightLength + 1;
        }
        longest = std::max(longest, left_length + right_length);//可能包含当前节点以及从左右子节点开始的最长同值路径
        return std::max(left_length, right_length);
    }
};

首先看题所给TreeNode二叉树的结构,每个节点有一个val值,以及左右子节点.并含有三种构造函数

定义一个longest变量,用于存储最长同值路径.
定义一个ArrowLength递归函数,用于计算从当前节点开始的最长同值路径.如果当前节点为空,返回0.计算左右子树的最长同值路径,并且判断左右子节点是否和当前节点的值相同,如果相同,路径长度+1.最后返回左右子树的最长同值路径.最后返回longest变量.

值得注意的是,在计算longest时,可能包含当前节点以及从左右子节点开始的最长同值路径,所以需要取最大值.

longest = std::max(longest, left_length + right_length);

测试用例

C++: