[LeetCode] 236. Lowest Common Ancestor of a Binary Tree

Problem: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

Search p, q in binary tree.  If both p and q are in the left sub-tree, the lowest common ancestor is in the left sub-tree. If both p and q are in the right sub-tree, the lowest common ancestor is in the right sub-tree. otherwise the current node is the lowest common ancestor.

# 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':
        
        def postorder(node):
            if not node:
                return False, None
            
            leftFound, leftAncestor = postorder(node.left)
            if leftAncestor:
                return True, leftAncestor
            
            rightFound, rightAncestor = postorder(node.right)
            if rightAncestor:
                return True, rightAncestor
            
            if (leftFound or rightFound) and node in [p, q] :
                return True, node
            
            if leftFound and rightFound:
                return True, node
            
            return rightFound or leftFound or node in [p, q], None
        
        return postorder(root)[1]

Edited on 06/30/2021. Use postorder traversal to locate node p and q.

Edited on 11/07/2021. Simplify the postorder based solution. Because all node.val is unique, the order to find p or q does not matter.