NeetCode 150 [Tree]medium:Lowest Common Ancestor in Binary Search Tree

NeetCodeのSolutionを書いていく

Lowest Common Ancestor in Binary Search Tree

問題

すべてのノードの値がユニークである2分木が与えられます。
ノードp,qの値が与え荒れたときに、共通となる祖先の最小値を返します。

制約

• ノード数は2以上100以下
• ノードの値は-100以上100以下
• pとqは必ず異なり、ツリーに存在する

計算量：O(h) hはツリーの高さ
メモリ：O(h)

例

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

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

メモ

Binary Search Treeとは
左側の子孫の値 <= 自らの値 <= 右側の子孫の値
になるように作られた構造とのこと。多分昔勉強したはずだけど完全に忘れている。
この特性を使って解く模様。

ヒントを読んでも意味がわからず、Solutionを見てようやく理解できた。

• ルートから探索を始めて、p,qの数字が自分と同じであれば自分自身が答えとなる
• p,qの探索が左右に別れたら自分自身が答えとなる
• それ以外であれば左なら左、右なら右をルートとして再帰的に検索を繰り返す
  """

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        # ルートから探索を始めて、p,qの数字が自分と同じであれば自分自身が答えとなる
        # p,qの探索が左右に別れたら自分自身が答えとなる
        # それ以外であれば左なら左、右なら右をルートとして再帰的に検索を繰り返す
        if root.val == p.val or root.val == q.val:
            return root

        if (p.val < root.val < q.val) or (q.val < root.val < p.val):
            return root

        if p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)

        return self.lowestCommonAncestor(root.right, p, q)