Common ancestor of binary tree and binary search tree (Python)

The common ancestor of binary tree and binary search tree Power button

• • 236. The nearest common ancestor of a binary tree
  • 235. The nearest common ancestor of a binary search tree

236. The nearest common ancestor of a binary tree

Their thinking ：
Judging the common ancestor of a binary tree consists of the following three situations .

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root:
return None
if root is p or root is q: return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
# situation 1, If p, q In the left and right subtrees , Returns the current node 
if left and right:
return root
# situation 2, If p, q Not in the left and right subtrees , Returns an empty 
if left is None and right is None:
return None
# situation 3, If p, q Only one exists in root In the node that is the root , Returns the current node 
return right if left is None else left

235. The nearest common ancestor of a binary search tree

Their thinking ：
When considering the common ancestor of binary search tree , We should combine the properties of binary search tree .

class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
# The current node is greater than p, q Go to the left subtree to find 
if p.val < root.val and q.val < root.val:
return self.lowestCommonAncestor(root.left, p ,q)
# The current node is less than p, q Go to the right subtree to find 
elif p.val > root.val and q.val > root.val:
return self.lowestCommonAncestor(root.right, p ,q)
# Returns the current node 
else:
return root

The above two problems can be solved in the following ways .

Binary search tree is actually a special binary tree .

And for the smallest common ancestor of a binary tree , The following code contains three judgment cases of question 1 .

class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root or root is p or root is q:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p , q)
# There are three cases involving the problem of binary tree 
if not left:
return right
if not right:
return left
return root