Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “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).”
Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]
_______3______
/
___5__ ___1__
/ /
6 _2 0 8
/
7 4
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of of nodes 5 and 1 is 3.
Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself
according to the LCA definition.
Note:
- All of the nodes' values will be unique.
- p and q are different and both values will exist in the binary tree.
Solution1:
class Solution:
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
def judge(root,child):
if not root or not child:
return False
if root==child:
return True
return judge(root.left,child) or judge(root.right,child)
dic = collections.defaultdict(bool)
if root is None:
return None
dic[root] = True
dic[root.left] = judge(root.left,p) and judge(root.left,q)
dic[root.right] = judge(root.right,p) and judge(root.right,q)
if not dic[root.left] and not dic[root.right]:
return root
elif dic[root.left]:
return self.lowestCommonAncestor(root.left,p,q)
else:
return self.lowestCommonAncestor(root.right,p,q)
29 / 31 test cases passed.
root是p和q的LCA,当且仅当p和q都是root的子节点或其本身，root.left和root.right都不是。
Solution2:
class Solution:
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
if root is None or root==p or root==q: #发现目标节点则通过返回值标记该子树发现了某个目标结点
return root
left = self.lowestCommonAncestor(root.left,p,q) #查看左子树中是否有目标结点，没有为null
right = self.lowestCommonAncestor(root.right,p,q) #查看右子树是否有目标节点，没有为null
if left is not None and right is not None: #都不为空，说明左右子树都有目标结点，则公共祖先就是本身
return root
return left if left is not None else right #You'd better use 'left is not None' rather than 'not left'