687.最长同值路径

问题

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

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

示例 1:

输入:

graph TD
    A[5] --> B[4]
    A --> C[5]
    B --> D[1]
    B --> E[1]
    C --> F[ ]
    C --> G[5]
    
    style F fill:transparent,stroke:transparent

输出 $2$

示例 2:

输入:

graph TD
    A[1] --> B[4]
    A --> C[5]
    B --> D[4]
    B --> E[4]
    C --> F[ ]
    C --> G[5]
    
    style F fill:transparent,stroke:transparent

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

解法

基本想法就是深度优先遍历。遍历时，判断左右儿子的值与自己的值是否相等，相等则result++，否则置为0即可。没有什么难度。

代码

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int result = 0;
    public int longestUnivaluePath(TreeNode root) {
        if (root != null) {
            dfs(root);
        }
        return result;
    }
    private int dfs(TreeNode root) {
        if (root ==null) {
            return 0;
        }
        
        //计算左子树的同值路径
        int left = dfs(root.left);
        //判断左儿子与自己的值是否相等，相等则++ 否则置为0
        if (root.left == null || root.val !=root.left.val) {
            left = 0;
        } else {
            left ++;
        }
        //计算右子树的同值路径
        int right = dfs(root.right);
        //同左儿子的判断
        if (root.right == null || root.val !=root.right.val) {
            right = 0;
        } else {
            right ++;
        }
        //需要注意的是这里的max为left+right与result的判断。
        result = Math.max(left + right,result);
        return Math.max(left, right);
    }
}