Lowest common ancestor of a binary tree (not a BST)
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
The LCA is defined as: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
# If looking for me, return myself
if root == p or root == q:
return root
left = right = None
# else look in left and right child
if root.left:
left = self.lowestCommonAncestor(root.left, p, q)
if root.right:
right = self.lowestCommonAncestor(root.right, p, q)
# if both children returned a node, means
# both p and q found so parent is LCA
if left and right:
return root
else:
# either one of the chidren returned a node, meaning either p or q found on left or right branch.
# Example: assuming 'p' found in left child, right child returned 'None'. This means 'q' is
# somewhere below node where 'p' was found we dont need to search all the way,
# because in such scenarios, node where 'p' found is LCA
return left or rightRelated 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.
You are given a 0-indexed array of unique strings words.
A palindrome pair is a pair of integers (i, j) such that:
0 <= i, j < words.length,
i != j, and
words[i] + words[j] (the concatenation of the two strings) is a palindrome.
Return an array of all the palindrome pairs of words.
You must write an algorithm with O(sum of words[i].length) runtime complexity.
Given a 1-indexed integer array prices, where prices[i] is the price of a particular stock on the ith day, your task is to select some of the elements of prices such that your selection is linear.
A selection indexes, where indexes is a 1-indexed integer array of length k which is a subsequence of the array [1, 2, ..., n], is linear if:
For every 1 < j <= k, prices[indexes[j]] - prices[indexes[j - 1]] == indexes[j] - indexes[j - 1]
The score of a linear selection is the sum of the prices at those indices, return the maximum score that a linear selection can have given the input.