BT 中 LCA 的经典问题：给定二叉树，找到最低的共同祖先。我找到了一个 Python2 解决方案，但不知道如何在 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
我是 Python3 的新手，并试图在 Python3 中修复这个错误，我正在尝试下面，但没有工作。
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]