毎日のアルゴリズム: 二分木の最小共通祖先

この記事はWeChatの公開アカウント「3分でフロントエンドを学ぶ」から転載したもので、著者はsisterAnです。この記事を転載する場合は、「3分で学ぶフロントエンド」公式アカウントまでご連絡ください。

木の基礎については、こちらをご覧ください: 初心者のための木

バイナリ ツリーが与えられた場合、ツリー内の指定された 2 つのノードの最下位の共通祖先を見つけます。

Baidu 百科事典では、LCA を次のように定義しています。「ルート付きツリー T 内の 2 つのノード p と q の場合、LCA は、x が p と q の両方の祖先であり、x の深さが可能な限り大きいノード x です (ノードはそれ自身の祖先になることもできます)。」

たとえば、次の二分木があるとします: root = [3,5,1,6,2,0,8,null,null,7,4]

例1:

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

例2:

入力: root = [3,5,1,6,2,0,8, null , null ,7,4], p = 5, q = 4
出力: 5
説明: ノード 5 とノード 4 の LCA はノード 5 です。定義上、LCA はノード自体になる可能性があるからです。

例:

• すべてのノード値は一意です。
• p と q は異なるノードであり、両方とも指定されたバイナリ ツリー内に存在します。

答え: 再帰実装

解決：

ツリーが空のツリーであるか、p または q のいずれかのノードがルート ノードである場合、p と q の最も近い共通ノードがルート ノードになります。

そうでない場合、つまりバイナリ ツリーが空のツリーではなく、p と q がルート以外のノードである場合は、左と右のサブツリーを再帰的にトラバースして、左と右のサブツリーの最も近い共通の祖先を取得します。

• pノードとqノードが左右のサブツリーのLCAに存在する場合、pノードとqノードが左右のサブツリーのルートノードに分布していることを意味します。このとき、バイナリツリーのLCAはルート
• 左のサブツリー内のノード p と q の LCP が空の場合、ノード p と q は左のサブツリーに配置され、最終的なバイナリ ツリーの LCP は右のサブツリー内のノード p と q の LCP になります。
• 右サブツリー内のノード p と q の最新の共通祖先が空の場合、左サブツリー内のノード p と q の最新の共通祖先が空の場合と同じ判断ロジックが適用されます。
• 左と右のサブツリー内の p ノードと q ノードの最も近い共通祖先が空の場合、null が返されます。

コード実装:

 const lowestCommonAncestor =関数(ルート、p、q) {
    if(root == null || root == p || root == q)ルートを返す
    const left = lowestCommonAncestor ( root.left , p, q)
    定数right = lowestCommonAncestor(root.right , p, q)
    if(左=== null )戻り値 右 
    if(右=== null )戻り値 左 
ルートを返す
};

複雑性分析:

時間計算量: O(n)

空間計算量: O(n)