687.最长同值路径

发表于 | 分类于
字数统计: 386 | 阅读时长 ≈ 1

一、题目描述

给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。

注意：两个节点之间的路径长度由它们之间的边数表示。

示例 1:

输入:

1
2
3
4
5
    5
   / \
  4   5
 / \   \
1   1   5

输出:

1
2

示例 2:

输入:

1
2
3
4
5
    1
   / \
  4   5
 / \   \
4   4   5

输出:

1
2

注意: 给定的二叉树不超过10000个结点。 树的高度不超过1000。

二、题解

1.递归

1.1 思路

此题与543.二叉树的直径和563.二叉树的坡度的思路非常相似

1.在递归过程中，左右子树中，与当前根节点值相等的节点数目的和的最大值

1.2 代码

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
//左右子树中，与根节点值相等的节点数目的和的最大值
int help(struct TreeNode *root, int *num)
{
    if (root == NULL)
        return 0;
    int leftLen = help(root->left, num);
    int rightLen = help(root->right, num);
    int l = 0, r = 0;
    if (root->left != NULL && root->left->val == root->val)//向左遍历与根节点相等的子节点
        l = 1 + leftLen;
    if (root->right != NULL && root->right->val == root->val)//向左遍历与根节点相等的子节点
        r = 1 + rightLen;
    *num = *num < (l + r) ? (l + r) : *num;
    return l > r ? l : r;
}
int longestUnivaluePath(struct TreeNode *root)
{
    if (root == NULL || (root->left == NULL && root->right == NULL))
        return 0;
    int res = 0;
    help(root, &res);
    return res;
}