最长同值路径

题面

给定一个二叉树,找到最长的路径,这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
两个节点之间的路径长度由它们之间的边数表示,下面输出 2

              5
             / \
            4   5
           / \   \
          1   1   5

分析

  • 将不同值树拆解成多个同值子树,求各子树的最大路径,取长
  • 确定同值子树的根节点,同值树的参照值,如示例层序遍历中选用第一个5为同值子树根,而非下层5
  • 递归求同值树单边最大路径,递归体内比较取该同值树最长路径,对于同值树而言最长路径必经过根节点

拆解

不同值树拆解为同值子树过程

最长同值路径
上述拆解,参考标准值依次为5,4,1,1, 上层向下层带值传递,父子不同拆分

同值子树最大路径,必经过根节点
最长同值路径
每个同值连续节点最长路径,即左路径最长+右最长

代码

func longestUnivaluePath(root *TreeNode) int {
    var rs int
    var dfs func(*TreeNode,int) int
    dfs = func(root *TreeNode, val int) int{
        if root.Val != val {    // 隐性表达该条件体外,当前节点值与参照标准值相等
            dfs(root,root.Val)  // 选定拆解为同值节点子树根节点,及同值参照物
            return -1           // 修正同值连续节点递归+1带来的副作用
        }

        l,r:= 0,0
        if root.Left != nil {
            l = dfs(root.Left, val)+1  // 父子左连续,假定左值与参照值相同,计数加1
        }
        if root.Right != nil {
            r= dfs(root.Right, val)+1  // 右连续计数
        }

        if cur := l+r; cur > rs {  // 最大连续路径数
            rs = cur
        }
        if l > r {  // 取单边连续最大值
            return l
        }
        return r
    }
    if root != nil {
        dfs(root, root.Val)
    }
    return rs
}
本作品采用《CC 协议》,转载必须注明作者和本文链接
pardon110
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
开发者 @ 社科大
文章
133
粉丝
24
喜欢
100
收藏
54
排名:107
访问:8.9 万
私信
所有博文
社区赞助商