687. 最长同值路径

题目描述

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

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

示例

输入:

              5
             / \
            4   5
           / \   \
          1   1   5
输出:
2

思路

1.可以根据题意推导出本题的公式：rootPathVal = Math.max(leftPathVal,rightPathVal)。
2.可以看出此题可以使用递归思想求解。
3.若leftVal == rootVal，则leftPathVal = leftPathVal + 1，否则leftVal = 0 ,因为只有相同时，leftVal才可以作为同路径的参考；rightVal也是同理。

Java代码实现

class Solution {
    private int res = 0;
    public int longestUnivaluePath(TreeNode root) {
        if(root == null){
            return 0;
        }
        longestUnivaluePathBFS(root);
        return res;
    }

    public int longestUnivaluePathBFS(TreeNode root) {
        if(root == null){
            return 0;
        }

        int left = longestUnivaluePathBFS(root.left);
        int right = longestUnivaluePathBFS(root.right);

        if(root.left != null && root.left.val == root.val){
            left = left + 1;
        }else{
            left = 0;
        }

        if(root.right != null && root.right.val == root.val){
            right = right + 1;
        }else{
            right = 0;
        }

        res = Math.max(res,left+right);

        return Math.max(left,right);
    }
}

Golang代码实现

var maxVal int = 0

func longestUnivaluePath(root *TreeNode) int {
    longestUnivaluePathBFS(root)
    return maxVal
}

func longestUnivaluePathBFS(root *TreeNode) int {
    if root == nil{
        return 0
    }

    left := longestUnivaluePathBFS(root.Left)
    right := longestUnivaluePathBFS(root.Right)

    if root.Left != nil && root.Left.Val == root.Val{
        left = left + 1
    }else {
        left = 0
    }

    if root.Right != nil && root.Right.Val == root.Val{
        right = right + 1
    }else {
        right = 0
    }

    if left+right>maxVal{
        maxVal = left+right
    }

    if left>right {
        return left
    }else {
        return right
    }
}