687. 最长同值路径(一般)

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

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

示例 1:

输入:      5
         / \
        4   5
       / \   \
      1   1   5

输出:2

示例 2:

输入:      1
         / \
        4   5
       / \   \
      4   4   5

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-univalue-path

思路：

  1. 设计一个递归函数
  2. 递归函数的返回值
    1. 我们希望这个函数能够得到：从 node 节点开始，向下出发，最长的同值路径长度
    2. 因为路径的一个方向是通向 node 的父节点，所以另一个方向只能从 node 的左或右节点中选择至多一个
  3. 递归函数的出口
    1. 如果 node 为空，返回 0
  4. 递归函数的逻辑
    1. 当我们递归调用 node->left 和 node->right 时，就可以得到左/右子树与其数值相同节点的长度
    2. 只需要判断左/右子树的数值与根节点的数值是否相同，不相同的话就舍弃，相同的话长度就加一
    3. 那么与 node 值相同的路径长度就是左/右两条路中较长的
  5. 递归函数只能取得 node 的同值路径长度，这里还有一些其他情况需要考虑
    1. 如果最长的路径是由一个其他数值的子节点开始向下出发的情况，在递归中间因为数值不同被舍弃了
    2. 是由一个子节点，向左右两个方向同时向下出发的情况（情况 1）
  6. 在递归函数的参数中使用一个引用变量，记录全局最大值
    1. 当计算出一个节点的返回值时，将以这个节点，连接左右两边的路径长度，更新到全局最大值
    2. 然后再返回
  7. 这个全局最大值包含了以上所有情况，就是题目的答案

作者：ikaruga
链接：https://leetcode-cn.com/problems/longest-univalue-path/solution/687-by-ikaruga/

代码1：

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int res;
    public int longestUnivaluePath(TreeNode root) {
        res =0;
        dfs(root);
        return res;
    }
    public int dfs(TreeNode root){
        if(root==null)  return 0;
        int l_len = dfs(root.left);
        int r_len = dfs(root.right);
        int left = 0,right = 0;
        if(root.left!=null && root.val==root.left.val)
            left = l_len+1;
        if(root.right!=null && root.val == root.right.val)
            right = r_len+1;
        res = Math.max(res,left+right);
        return Math.max(left,right);
    }
}