235. Lowest Common Ancestor of a Binary Search Tree

Problem Statement

link: LeetCode.cn LeetCode

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

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).”

Example:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 Output: 6

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 Output: 2

Solution Approach

Method 1: Iteratively traverses the BST from the root to find the lowest common ancestor by comparing node values to the target node values. Method 2: Recursively traverses the BST and returns the lowest common ancestor by comparing node values and recursively calling the function for the left or right subtree accordingly. Method 3: Utilizes a recursive approach to traverse the BST, identifying the lowest common ancestor by recursively exploring both left and right subtrees. Method 4: Finds paths from the root to the target nodes using iterative traversal, then iterates over the paths to find the lowest common ancestor.

Algorithm

Method 1:

Start from the root and traverse down the BST iteratively. Compare the values of the current node with the values of nodes p and q. Update the ancestor node according to the positions of p and q, traversing left or right based on their values.

Method 2:

Recursively traverse the BST, starting from the root. Compare the values of the current node with the values of nodes p and q. Recursively call the function for the left or right subtree based on the values of p, q, and the current node.

Method 3:

Recursively traverse the BST, starting from the root. Check if the current node is None or matches either p or q, returning the current node if so. Recursively explore the left and right subtrees to find the lowest common ancestor. If both are found, return the current node as the LCA.

Method 4:

Utilize an iterative approach to find paths from the root to the target nodes p and q. Store the paths in lists by traversing the BST from the root to each target node. Iterate over the paths simultaneously to find the last common node before the paths diverge, which represents the lowest common ancestor.

Implement

    # 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':
        ancestor = root
        while True:
            if p.val < ancestor.val and q.val < ancestor.val:
                ancestor = ancestor.left
            elif p.val > ancestor.val and q.val > ancestor.val:
                ancestor = ancestor.right
            else:
                break
        return ancestor

    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if (root.val - p.val) * (root.val - q.val) <= 0:
            return root
        if p.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)
        else:
            return self.lowestCommonAncestor(root.right, p, q)    

    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or root == p or root == q:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if not left:
            return right
        if not right:
            return left
        return root

    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        def getPath(root, target):
            path = []
            node = root 
            while node != target:
                path.append(node)
                if node.val > target.val:
                    node = node.left
                else:
                    node = node.right
            path.append(node)
            return path

        p_path = getPath(root, p)
        q_path = getPath(root, q)
        res = None
        for i, j in zip(p_path, q_path):
            if i == j:
                res = i
        return res
        
   
      

    
    

Twitter  facebook  Email