問題演習: Lowest Common Ancestor in Binary Search Tree

今回は「Lowest Common Ancestor in Binary Search Tree」という問題です。難易度は「Easy」です。

問題

2 分探索木の 2 つのノードが与えられる。その 2 つのノードに共通する親ノードのうち、葉にもっとも近いものを返せ。ただし片方のノードが他方の親ノードの場合、その親ノードを共通する親ノードとする。

解答テンプレート

Javaの例を示します。

	public class Node {
	int value;
	Node left;
	Node right;
	Node(int x) { value = x; }
	}
	public class Solution {
	public Node lowestCommonAncestor(Node root, Node n1, Node n2) {
	// Write your code here.
	}
	}

view raw lca-in-bst.java hosted with ❤ by GitHub

入出力例

例として次の木を用いる。

      4
    /   \
   2     6

  / \   / \

 1   3 5   7

例えば、1 と 3 のノードが与えられた場合、共通の親ノードのうち葉にもっとも近いものは 2 なので、2 のノードを返す

2 と 7 の場合は 4 を返す。
5 と 6 の場合は 6 を返す。


それでは、解答と解説は次の投稿で。
---
シリコンバレーでエンジニアとして就職するには、アルゴリズムやプログラミング、システムデザインの問題が出題される面接を突破する必要があります。本サイトでは、シリコンバレーでエンジニアとして働き、面接官としての経験も豊富な筆者が、面接への対策に関する情報を配信しています。