687.longest-univalue-path.md

687. Longest Univalue Path

Test Cases

Edge / Corner Cases

The longest path does not pass the top-level root node.

Input: 
             5
            /
           5
        /     \
       5       5
     /   \       \
    5     5       5
         /
        5
Output: 5, not 3 or 4

Breakdowns

1. How to calculate the longest path without the restriction of the same value? (Pass the root node) 104. Maximum Depth of Binary Tree

2. How to calculate the longest path that may not pass the root node? 543. Diameter of Binary Tree

Postorder

We use DFS to find the longest univalue path at each node (We extend the path with the child nodes, downward).

For each node:

• Recursively find the longest univalue path from the child nodes.
• If the child node has the same value as the current node, we extend the path by 1.
• Compute the longest path that passes the current node from the child nodes.
• Update and keep track of the maximum path length.

先算子節點的距離，子節點的狀況 (是否相等) 先不管，先算！然後看子節點是否跟父節點值相同，是的話父節點就可以加上子節點的距離，串成更長的距離。

不論在哪個節點，我們都要先計算以當前的 root 為出發點的距離，算完後，我們再看 root 能否與前面的值串成更長的距離。

// Possible values of the tree:
    5          5          5
  /   \      /   \      /   \
 4     3    5     8    5     5

private var longestDistance = 0

fun longestUnivaluePath(root: TreeNode?): Int {
    getDistance(root)
    return longestDistance
}

private fun getDistance(root: TreeNode?): Int {
    if (root == null) return 0

    val left = getDistance(root.left)
    // The following code is wrong, because we need to traverse the child even if the value is not the same.
    // val left = if (root.left != null && root.`val` == root.left.`val`) {
    //     getDistance(root.left) + 1
    // } else {
    //     0
    // }
    val right = getDistance(root.right)

    val leftDistance = if (root.left != null && root.`val` == root.left.`val`) {
        left + 1
    } else {
        0
    }
    val rightDistance = if (root.right != null && root.`val` == root.right.`val`) {
        right + 1
    } else {
        0
    }
    longestDistance = maxOf(longestDistance, leftDistance + rightDistance)
    return maxOf(leftDistance, rightDistance)
}   

// Or equivalently, we calculate the number of nodes
private var longestNodes = 0
fun longestUnivaluePath(root: TreeNode?): Int {
    if (root == null) return 0
    // dfs(root, root.`val`)
    dfs(root)
    return longestNodes - 1
}

private fun dfs(root: TreeNode?): Int {
    if (root == null) return 0
    val left = dfs(root.left)
    val right = dfs(root.right)
    val leftNodes = if (root.left != null && root.`val` == root.left.`val`) {
        left
    } else 0
    val rightNodes = if (root.right != null && root.`val` == root.right.`val`) {
        right
    } else 0
    longestNodes = maxOf(longestPath, leftNodes + rightNodes + 1)
    return 1 + maxOf(leftNodes, rightNodes)
}

Or we can implement in the same way as 543. Diameter of Binary Tree:

For each root, we calculate the longest path based on the root value from left and right child nodes. (The longest path with the same root value)

// For the current node: `root` and `value`
                       dfs(root, value)
                             \ +1
                             root 
dfs(left, root.value)      /      \     dfs(right, root.value)
                         left     right

Then we check if we have the same value from our parent value, if yes, we can form a longer path with the parent node. (We extend the path with the parent node, upward)

private var longestDistance = 0

fun longestUnivaluePath(root: TreeNode?): Int {
    if (root == null) return 0
    getDistance(root, root.`val`) 
    return longestDistance
}

private fun getDistance(root: TreeNode?, parentValue: Int): Int {
    if (root == null) return 0
    
    // We calculate the longest path with the root value from left and right child nodes
    val left = getDistance(root.left, root.`val`)
    val right = getDistance(root.right, root.`val`)

    // We see if we can form a longer path that includes the root node.
    longestDistance = maxOf(longestDistance, left + right)

    // Then we see if we can form a longer path from our parent path.
    return if (root.`val` == parentValue) maxOf(left, right) + 1 else 0 
}