[Leetcode] 0235. 二分探索木の最小共通祖先

バイナリ検索ツリー (BST) が与えられた場合、BST 内の 2 つの指定されたノードの最下位共通祖先 (LCA) ノードを検索します。

によると、 WikipediaにおけるLCAの定義: 「最下位共通祖先は2つのノード間で定義されます p そして q 最下位ノードとして T 両方を兼ね備えた p そして q 子孫として（ 自身の子孫となるノード）」

例 1:

入力： 根 = [6,2,8,0,4,7,9,null,null,3,5]、p = 2、q = 8
出力： 6
説明： ノード 2 と 8 の LCA は 6 です。

例 2:

入力： 根 = [6,2,8,0,4,7,9,null,null,3,5]、p = 2、q = 4
出力： 2
説明： LCA 定義によれば、ノードは自身の子孫になることができるため、ノード 2 と 4 の LCA は 2 です。

例 3:

入力： 根 = [2,1]、p = 2、q = 1
出力： 2

制約:

• ツリー内のノードの数は範囲内です [2, 10 5 ].
• -10 9 <= ノード値 <= 10 9
• 全て Node.val は 個性的.
• p != q
• p そして q BST に存在します。