# Lowest Common Ancestor with N nodes

Similar with finding lowest common ancestor of two nodes, we can extend this function to N nodes.

The method buildTree in the solution is in order to building a tree instantly by given strings.

```# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None

class Solution:
def buildTree(self, inorder, postorder):
if not inorder or not postorder:
return None

while postorder:
if postorder[-1] not in inorder:
postorder.pop()
else:
break

if len(postorder) == 1:
return TreeNode(postorder)

else:
node = TreeNode(postorder[-1])
in_index = inorder.index(postorder[-1])
node.left = self.buildTree(inorder[:in_index], postorder[:-1])
node.right = self.buildTree(inorder[in_index + 1:], postorder[:-1])
return node

def find(self, root, nodes):
if not root:
return None
else:
if root.val in nodes:
return root

left = self.find(root.left, nodes)
right = self.find(root.right, nodes)

if left and right:
return root

return right if not left else left

if __name__ == "__main__":
obj = Solution()
root = obj.buildTree([6, 5, 7, 2, 4, 3, 0, 1, 8], [6, 7, 4, 2, 5, 0, 8, 1, 3])
nodes = [0, 1, 8]
result = obj.find(root, nodes)
print(result.val)
```

# House Robber III

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

`Input: [3,2,3,null,3,null,1]        3      / \    2   3      \   \         3   1 Output: 7  Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.`

Example 2:

`Input: [3,4,5,1,3,null,1]            3          / \        4   5      / \   \     1   3   1 Output: 9 Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.`
```# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def rob(self, root: TreeNode) -> int:
def superrob(node):
# returns tuple of size two (now, later)
# now: max money earned if input node is robbed
# later: max money earned if input node is not robbed

# base case
if not node: return (0, 0)

# get values
left, right = superrob(node.left), superrob(node.right)

# rob now
now = node.val + left + right

# rob later
later = max(left) + max(right)

return (now, later)

return max(superrob(root))```

# Lowest Common Ancestor with N nodes

Today, I have taken an interview from Wechat.

To be honest, this question is easy, but I do not have sufficient time to complete coding. Maybe I took too much time in same trivial points with the “VERY PROFESSIONAL” interviewer.

The actual question is find the lowest common ancestor of three given nodes, but I thought we can expend this question to N nodes. For testing this question rapidly, I reuse the previous code of constructing a binary tree by the in-order and post-order traversals.