235. Lowest Common Ancestor of a

题目描述

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

Given binary search tree: root = [6,2,8,0,4,7,9,null,null,3,5]

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

Note:

All of the nodes' values will be unique.
p and q are different and both values will exist in the BST.

Qiang的思路

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        while True:
            tmp = root
            if root.val == p.val or root.val == q.val:
                break
            if root.val > p.val and root.val > q.val:
                root = root.left
            elif root.val < p.val and root.val < q.val:
                root = root.right
            else:
                break
        return tmp

class Solution:
    def get_path(self, root, node, path):
        path.append(root)
        if node.val == root.val:
            return
        elif node.val > root.val:
            self.get_path(root.right, node, path)
        else:
            self.get_path(root.left, node, path)


    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        path_p = []
        self.get_path(root, p, path_p)
        path_q = []
        self.get_path(root, q, path_q)
        for i in range(min(len(path_q), len(path_p))):
            if path_q[i] != path_p[i]:
                return path_p[i - 1]
        return path_p[min(len(path_q), len(path_p)) - 1]