Leetcode Problem 687. Longest Univalue Path

687. Longest Univalue Path

Leetcode Solutions

Depth-First Search for Longest Univalue Path

  1. Define a recursive helper function dfs(node) that returns the length of the longest path starting from node and consisting of nodes with the same value as node.
  2. If node is null, return 0.
  3. Recursively call dfs(node.left) and dfs(node.right) to get the longest paths for the left and right subtrees.
  4. If node.left is not null and has the same value as node, include the left path in the current path length. Otherwise, set the left path length to 0.
  5. Similarly, if node.right is not null and has the same value as node, include the right path in the current path length. Otherwise, set the right path length to 0.
  6. Update the global maximum path length if the sum of the left and right path lengths is greater than the current maximum.
  7. Return the maximum of the left and right path lengths plus 1 to account for the current node.
  8. Call dfs(root) and return the global maximum path length.
UML Thumbnail

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...