LeetCode 687. 最长同值路径

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

Tags

tree | recursion

Companies

google

题目:

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

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

提示:

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

思路

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

c++
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++: