Longest univalue path in a binary tree
Given the root of a binary tree, return the length of the longest path, where each node in the path has the same value. This path may or may not pass through the root.
The length of the path between two nodes is represented by the number of edges between them.
class Solution(object):
def longestUnivaluePath(self, root):
longest = [0]
def traverse(node):
if not node:
return 0
left_len, right_len = traverse(node.left), traverse(node.right)
left = (left_len + 1) if node.left and node.left.val == node.val else 0
right = (right_len + 1) if node.right and node.right.val == node.val else 0
longest[0] = max(longest[0], left + right)
return max(left, right)
traverse(root)
return longest[0]Related Problems
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Given the root of a binary tree, flatten the tree into a "linked list":
The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
The "linked list" should be in the same order as a pre-order traversal of the binary tree.
Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.
A leaf is a node with no children.
Given an m x n board of characters and a list of strings words, return all words on the board.
Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.