235. Lowest Common Ancestor of a Binary Search Tree
235. Lowest Common Ancestor of a Binary Search Tree
如果大于最大值，则所求在左子树，如果小于最小值，则所求在右子树，否则，返回当前节点
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
#循环
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
while root:
if root.val > max(p.val, q.val):
root = root.left
elif root.val < min(p.val, q.val):
root = root.right
else:
return root
#递归
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
if root.val > max(p.val, q.val):
return self.lowestCommonAncestor(root.left, p, q)
elif root.val < min(p.val, q.val):
return self.lowestCommonAncestor(root.right, p, q)
else:
return root
#找路径后比较
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
l1 = self.findPath(root, p)
l2 = self.findPath(root, q)
res = root
for i in range(min(len(l1), len(l2))):
if l1[i] == l2[I]:
res = l1[I]
else:
break
return res
def findPath(self, root, p):
res = []
while root.val != p.val:
res.append(root)
if root.val > p.val:
root = root.left
else:
root = root.right
res.append(p)
return res
236. Lowest Common Ancestor of a Binary Tree
236. Lowest Common Ancestor of a Binary Tree
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
mydic = {}
l1 = self.findPath(root, p)
l2 = self.findPath(root, q)
res = root
for i in range(min(len(l1), len(l2))):
if l1[i] == l2[I]:
res = l1[I]
else:
break
return res
def findPath(self, root, p):
res = []
mydic = {}
qu = [root]
while qu:
node = qu.pop(0)
if node == p:
break
else:
if node.left:
qu.append(node.left)
mydic[node.left] = node
if node.right:
qu.append(node.right)
mydic[node.right] = node
while node != root:
res.append(node)
node = mydic[node]
res.append(root)
return res[::-1]
