Classic problem of LCA in BT: Given a Binary Tree find the lowest common ancestor. I found a Python2 solution but don't know how to fix it in Python3.
# This is Python2, but having error in Python3 such that
# parent += node if all(subs) else max(subs),
# TypeError: '>' not supported between instances of 'NoneType' and 'NoneType'`
# lca.py
class Solution:
def lowestCommonAncestor(self, root, p, q):
answer = []
stack = [[root, answer]]
while stack:
top = stack.pop()
(node, parent), subs = top[:2], top[2:]
if node in (None, p, q):
parent += node,
elif not subs:
stack += top, [node.right, top], [node.left, top]
else:
parent += node if all(subs) else max(subs), # this is the problem in Python3
return answer[0]
s = Solution()
root = tree.create_tree3()
p = tree.find(root, 6)
q = tree.find(root, 1)
print(f'p = {p}, q = {q}')
lca = s.lowestCommonAncestor(root, p, q)
print(f"lca = {lca}")
# tree.py
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def __repr__(self):
return str(self.val)
def find(root, val):
if root is None:
return None
if root.val == val:
return root
left = find(root.left, val)
right = find(root.right, val)
if left is not None:
return left
else:
return right
"""
3
5 1
6 2 0 8
7 4
"""
def create_tree3():
n3 = TreeNode(3)
n5 = TreeNode(5)
n1 = TreeNode(1)
n6 = TreeNode(6)
n2 = TreeNode(2)
n0 = TreeNode(0)
n8 = TreeNode(8)
n7 = TreeNode(7)
n4 = TreeNode(4)
n3.left, n3.right = n5, n1
n5.left, n5.right = n6, n2
n1.left, n1.right = n0, n8
n2.left, n2.right = n7, n4
return n3
I'm a newbie of Python3 and trying to fix this error in Python3, and I'm trying below, but not working.
class Solution:
def lowestCommonAncestor(self, root, p, q):
answer = []
stack = [[root, answer]]
while stack:
top = stack.pop()
(node, parent), subs = top[:2], top[2:]
if node in (None, p, q):
parent += node,
elif not subs:
stack += top, [node.right, top], [node.left, top]
else:
if subs[0] and subs[1]:
parent += node
else: # not sure how to fix the below part which is not working either
if subs[0] and not subs[1]:
parent += subs[0]
elif not subs[0] and subs[1]:
parent += subs[1]
elif not subs[0] and not subs[1]:
parent += None
return answer[0]