687.最长同路径值

youzhihua · · 493 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

题目描述

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

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

示例

输入:

              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
    }
}

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:youzhihua

查看原文:687.最长同路径值

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

493 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传