describe

Given a binary search tree (BST), find the lowest common ancestor (LCA) 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 1:

Input: root = [6,2,8,0,4,7,9, null, null, 3, 5), p = 2, q = 8 Output: 6 Explanation: The LCA of nodes 2 and 8 is 6.Copy the code

Example 2:

Input: root = [6,2,8,0,4,7,9, null, null, 3, 5), p = 2, q = 4 Output: 2 Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.Copy the code

Example 3:

Input: root = [2,1], p = 2, q = 1
Output: 2
Copy the code

Note:

The number of nodes in the tree is in the range [2, 10^5]. -10^9 <= Node.val <= 10^9 All Node.val are unique. p ! = q p and q will exist in the BST.Copy the code

parsing

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in BST. You can do it the simplest way, find the path from the root node to P, and also find the path from the root node to Q, traverse both paths from left to right at the same time, and find the previous node where the first different node appeared is the LCA they’re looking for. Because the constraints in the problem are very loose, this method does not time out.

answer

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def __init__(self):
        self.paths = []
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        
        self.dfs(root, [], p)
        self.dfs(root, [], q)
        path_p = self.paths[0]
        path_q = self.paths[1]
        idx = 0
        while idx<min(len(path_p), len(path_q)) and path_p[idx].val==path_q[idx].val:
            idx += 1
        return path_p[idx-1]
    
    def dfs(self, root, path, t):
        if not root: return
        if root == t:
            path.append(root)
            self.paths.append(path)
            return 
        if root.left:
            self.dfs(root.left, path+[root], t)
        if root.right:
            self.dfs(root.right, path+[root], t)
            

        

           
        	      
		
Copy the code

The results

Runtime: 96 ms, Given Python online submissions for critical Common Ancestor of a Binary Search Tree. In the linked list, the submissions are linked to the linked list in the linked list.Copy the code

parsing

In addition, we can define a DFS to indicate the number of p or q contained in the subtree with a node as the root node. It may be 0 to indicate that p or Q is not included, 1 to indicate that only P or Q is included, and 2 to indicate that both are included, because recursion returns results from bottom up. When 2 is present for the first time and result is null, this object is LCA.

answer

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def __init__(self):
        self.result = None
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        self.dfs(root, p, q)
        return self.result
    
    def dfs(self, root, p, q):
        if not root: return 0
        count  = self.dfs(root.left, p, q) + self.dfs(root.right, p, q) 
        if root == p or root == q: 
            count += 1
        if count == 2 and self.result==None:
            self.result = root
        return count
            

        
Copy the code

The results

Runtime: 72 ms, Given Python online submissions for critical Common Ancestor of a Binary Search Tree. Linked to the linked list in the linked list in the linked list.Copy the code

Original link: leetcode.com/problems/lo…

Your support is my biggest motivation