最长同值路径

题面

给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
两个节点之间的路径长度由它们之间的边数表示,下面输出 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 协议》，转载必须注明作者和本文链接