题目标题

查找二叉树任意两个节点的最近公共祖先

参考解析
  1. class TreeNode:
  2. def __init__(self, val):
  3. self.val = val
  4. self.left, self.right = None, None
  5. class Solution:
  6. """
  7. @param: root: The root of the binary search tree.
  8. @param: A: A TreeNode in a Binary.
  9. @param: B: A TreeNode in a Binary.
  10. @return: Return the least common ancestor(LCA) of the two nodes.
  11. """
  12. def lowestCommonAncestor(self, root, A, B):
  13. # A&B=>LCA
  14. # !A&!B=>None
  15. # A&!B=>A
  16. # B&!A=>B
  17. if(root is None or root==A or root==B):
  18. return root #若root为空或者root为A或者root为B,说明找到了A和B其中一个
  19. left=self.lowestCommonAncestor(root.left,A,B)
  20. right=self.lowestCommonAncestor(root.right,A,B)
  21. if(left is not None and right is not None):
  22. return root #若左子树找到了A,右子树找到了B,说明此时的root就是公共祖先
  23. if(left is None): #若左子树是none右子树不是,说明右子树找到了A或B
  24. return right
  25. if(right is None): #同理
  26. return left
  27. return None
  28. a=Tree = TreeNode(2)
  29. b=Tree.left = TreeNode(1)
  30. c=Tree.right = TreeNode(3)
  31. d=b.left=TreeNode(4)
  32. s = Solution()
  33. print(s.lowestCommonAncestor(a,b,d).val)