algorithm - 二分木で2つのノードの最も低い共通の祖先を見つける方法は?

Question

ここでの二分木は、必ずしも二分探索木である必要はありません。
構造は次のように取ることができます -

struct node {
    int data;
    struct node *left;
    struct node *right;
};

私が友人と一緒に解決できる最大の解決策は、このようなものでした -この二分木
を考えてみましょう:

順序通りのトラバーサルの結果 - 8、4、9、2、5、1、6、3、7

そして、ポストオーダートラバーサルは、8、9、4、5、2、6、7、3、1 を生成します。

したがって、たとえば、ノード 8 と 5 の共通の祖先を見つけたい場合は、順序付けされたツリートラバーサルで 8 と 5 の間にあるすべてのノードのリストを作成します。この場合、たまたま [4, 9 、2]。次に、このリストのどのノードがポストオーダートラバーサルで最後に表示されるかを確認します。これは 2 です。したがって、8 と 5 の共通の祖先は 2 です。

このアルゴリズムの複雑さは、O(n) (順序/事後トラバーサルの場合は O(n)、配列内の単純な反復にすぎないため、残りのステップは O(n) であると私は信じています)。しかし、これが間違っている可能性が非常に高いです。:-)

しかし、これは非常に大雑把なアプローチであり、場合によってはうまくいかないかどうかはわかりません。この問題に対する他の (おそらくより最適な) 解決策はありますか?

score 109 · Accepted Answer

ノードから始まり、直接の子としてまたはrootを持つノードが見つかった場合、それが LCA です。(編集 - これはノードの値である場合、それを返す必要があります。そうでない場合、またはのいずれかが他方の直接の子である場合に失敗します。)pqpqpq

pそれ以外の場合、右 (または左) サブツリーとその左 (または右) サブツリーにあるノードが見つかった場合q、それは LCA です。

固定コードは次のようになります。

treeNodePtr findLCA(treeNodePtr root, treeNodePtr p, treeNodePtr q) {

        // no root no LCA.
        if(!root) {
                return NULL;
        }

        // if either p or q is the root then root is LCA.
        if(root==p || root==q) {
                return root;
        } else {
                // get LCA of p and q in left subtree.
                treeNodePtr l=findLCA(root->left , p , q);

                // get LCA of p and q in right subtree.
                treeNodePtr r=findLCA(root->right , p, q);

                // if one of p or q is in leftsubtree and other is in right
                // then root it the LCA.
                if(l && r) {
                        return root;
                }
                // else if l is not null, l is LCA.
                else if(l) {
                        return l;
                } else {
                        return r;
                }
        }
}

以下のコードは、いずれかが他の直接の子である場合に失敗します。

treeNodePtr findLCA(treeNodePtr root, treeNodePtr p, treeNodePtr q) {

        // no root no LCA.
        if(!root) {
                return NULL;
        }

        // if either p or q is direct child of root then root is LCA.
        if(root->left==p || root->left==q || 
           root->right ==p || root->right ==q) {
                return root;
        } else {
                // get LCA of p and q in left subtree.
                treeNodePtr l=findLCA(root->left , p , q);

                // get LCA of p and q in right subtree.
                treeNodePtr r=findLCA(root->right , p, q);

                // if one of p or q is in leftsubtree and other is in right
                // then root it the LCA.
                if(l && r) {
                        return root;
                }
                // else if l is not null, l is LCA.
                else if(l) {
                        return l;
                } else {
                        return r;
                }
        }
}

コードインアクション

score 74 · Accepted Answer

親ポインターがない場合、O(n) 時間の複雑さのアルゴリズムが最適であるという Nick Johnson の指摘は正しいです。そのアルゴリズムの単純な再帰バージョンについては、O(n) 時間で実行されるKinding の投稿のコードを参照してください。 .

ただし、ノードに親ポインターがある場合は、アルゴリズムを改善できることに注意してください。問題の両方のノードについて、ノードから開始し、親を前に挿入することにより、ルートからノードまでのパスを含むリストを作成します。

したがって、例の 8 の場合、次のようになります (ステップを表示): {4}, {2, 4}, {1, 2, 4}

問題の他のノードに対して同じことを行うと、次のようになります (手順は示されていません): {1, 2}

次に、作成した 2 つのリストを比較して、リストが異なる最初の要素、またはリストのいずれかの最後の要素のいずれか早い方を探します。

このアルゴリズムには O(h) 時間が必要です。ここで、h は木の高さです。最悪の場合、O(h) は O(n) と同等ですが、ツリーのバランスがとれていれば、それは O(log(n)) だけです。また、O(h) スペースも必要です。CEGRD の投稿に示されているコードを使用して、一定のスペースのみを使用する改良版が可能です。

ツリーがどのように構築されているかに関係なく、これが途中で変更せずにツリーに対して何度も実行する操作になる場合は、O(n) [線形] 時間の準備を必要とする他のアルゴリズムを使用できますが、ペアは O(1) [一定] 時間しかかかりません。これらのアルゴリズムの参照については、Wikipediaの最下位共通祖先問題のページを参照してください。(このリンクを最初に投稿したジェイソンの功績)

score 51 · Accepted Answer

これがJAVAの作業コードです

public static Node LCA(Node root, Node a, Node b) {
   if (root == null) {
       return null;
   }

   // If the root is one of a or b, then it is the LCA
   if (root == a || root == b) {
       return root;
   }

   Node left = LCA(root.left, a, b);
   Node right = LCA(root.right, a, b);

   // If both nodes lie in left or right then their LCA is in left or right,
   // Otherwise root is their LCA
   if (left != null && right != null) {
      return root;
   }

   return (left != null) ? left : right; 
}

score 30 · Accepted Answer

これまでの回答では、メモリ内のパスなど、再帰またはストアを使用しています。

ツリーが非常に深い場合、これらのアプローチはどちらも失敗する可能性があります。

これがこの質問に対する私の見解です。両方のノードの深さ (ルートからの距離) を確認して、それらが等しい場合は、両方のノードから共通の祖先に向かって安全に上に移動できます。深さの 1 つが大きい場合は、他のノードにとどまりながら、より深いノードから上に移動する必要があります。

コードは次のとおりです。

findLowestCommonAncestor(v,w):
  depth_vv = depth(v);
  depth_ww = depth(w);

  vv = v; 
  ww = w;

  while( depth_vv != depth_ww ) {
    if ( depth_vv > depth_ww ) {
      vv = parent(vv);
      depth_vv--;
    else {
      ww = parent(ww);
      depth_ww--;
    }
  }

  while( vv != ww ) {
    vv = parent(vv);
    ww = parent(ww);
  }

  return vv;

このアルゴリズムの時間計算量は O(n) です。このアルゴリズムの空間複雑度は O(1) です。

深さの計算に関しては、最初に次の定義を思い出すことができます。v がルートの場合、depth(v) = 0; それ以外の場合、depth(v) = depth(parent(v)) + 1. 次のように深さを計算できます。

depth(v):
  int d = 0;
  vv = v;
  while ( vv is not root ) {
    vv = parent(vv);
    d++;
  }
  return d;

score 9 · Accepted Answer

これは、バイナリツリーがどのように構成されているかによって異なります。おそらく、ツリーのルートを指定して目的のリーフノードを見つける何らかの方法があると思われます。選択したブランチが分岐するまで、それを両方の値に適用するだけです。

ルートが与えられたときに目的のリーフを見つける方法がない場合、通常の操作と最後の共通ノードを見つけるための唯一の解決策は、ツリーのブルートフォース検索です。

score 9 · Accepted Answer

これは次の場所にあります:- http://goursaha.freeoda.com/DataStructure/LowestCommonAncestor.html

 tree_node_type *LowestCommonAncestor(
 tree_node_type *root , tree_node_type *p , tree_node_type *q)
 {
     tree_node_type *l , *r , *temp;
     if(root==NULL)
     {
        return NULL;
     }

    if(root->left==p || root->left==q || root->right ==p || root->right ==q)
    {
        return root;
    }
    else
    {
        l=LowestCommonAncestor(root->left , p , q);
        r=LowestCommonAncestor(root->right , p, q);

        if(l!=NULL && r!=NULL)
        {
            return root;
        }
        else
        {
        temp = (l!=NULL)?l:r;
        return temp;
        }
    }
}

score 7 · Accepted Answer

2つのノードの共通の祖先を見つけるには:-

二分探索を使用してツリー内の指定されたノード Node1 を見つけ、このプロセスでアクセスしたすべてのノードを A1 などの配列に保存します。時間 - O(logn)、スペース - O(logn)
二分探索を使用してツリー内の特定の Node2 を見つけ、このプロセスでアクセスしたすべてのノードを A2 などの配列に保存します。時間 - O(logn)、スペース - O(logn)
A1 リストまたは A2 リストが空の場合、ノードは存在しないため、共通の祖先はありません。
A1 リストと A2 リストが空でない場合は、一致しないノードが見つかるまでリストを調べます。そのようなノードが見つかるとすぐに、その前のノードが共通の祖先になります。

これは、二分探索木で機能します。

score 7 · Accepted Answer

Tarjan のオフラインの最小共通祖先アルゴリズムで十分です ( Wikipediaも参照)。ウィキペディアには、この問題 (最低共通祖先問題) に関する詳細があります。

score 5 · Accepted Answer

私はJavaで説明的な写真と作業コードを試してみました.

http://tech.bragboy.com/2010/02/least-common-ancestor-without-using.html

score 3 · Accepted Answer

以下の再帰アルゴリズムは、バランスの取れた二分木に対して O(log N) で実行されます。getLCA() 関数に渡されたノードのいずれかがルートと同じである場合、ルートは LCA になり、調査を実行する必要はありません。

テストケース。 [1]ノード n1 と n2 の両方がツリー内にあり、親ノードのいずれかの側に存在します。 [2]ノード n1 または n2 のいずれかがルートで、LCA がルートです。 [3] n1 または n2 のみがツリー内にある場合、LCA はツリールートの左側のサブツリーのルートノードになるか、LCA はツリールートの右側のサブツリーのルートノードになります。

[4] n1 も n2 もツリーにないため、LCA はありません。 [5] n1 と n2 はどちらも一直線上に並んでおり、LCA は n1 または n2 のうちツリーのルートに近い方になります。

//find the search node below root
bool findNode(node* root, node* search)
{
    //base case
    if(root == NULL)
        return false;

    if(root->val == search->val)
        return true;

    //search for the node in the left and right subtrees, if found in either return true
    return (findNode(root->left, search) || findNode(root->right, search));
}

//returns the LCA, n1 & n2 are the 2 nodes for which we are
//establishing the LCA for
node* getLCA(node* root, node* n1, node* n2)
{
    //base case
    if(root == NULL)
        return NULL;

    //If 1 of the nodes is the root then the root is the LCA
    //no need to recurse.
    if(n1 == root || n2 == root)
        return root;

    //check on which side of the root n1 and n2 reside
    bool n1OnLeft = findNode(root->left, n1);
    bool n2OnLeft = findNode(root->left, n2);

    //n1 & n2 are on different sides of the root, so root is the LCA
    if(n1OnLeft != n2OnLeft)
        return root;

    //if both n1 & n2 are on the left of the root traverse left sub tree only
    //to find the node where n1 & n2 diverge otherwise traverse right subtree
    if(n1OnLeft)
        return getLCA(root->left, n1, n2);
    else
        return getLCA(root->right, n1, n2);
}

score 3 · Accepted Answer

先祖を見つけなければならない与えられたノードとの両方が同じサブツリーにあるroot限り、ツリー全体から下っていくだけです (つまり、それらの値は両方ともルートの値よりも小さいか、両方とも大きいことを意味します)。pq

これは、ツリーの残りの部分を見ずに、ルートから Least Common Ancestor までまっすぐに移動するため、かなり高速です。それを行ういくつかの方法。

反復、O(1) スペース

パイソン

def lowestCommonAncestor(self, root, p, q):
    while (root.val - p.val) * (root.val - q.val) > 0:
        root = (root.left, root.right)[p.val > root.val]
    return root

ジャワ

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    while ((root.val - p.val) * (root.val - q.val) > 0)
        root = p.val < root.val ? root.left : root.right;
    return root;
}

オーバーフローの場合は、(root.val - (long)p.val) * (root.val - (long)q.val) を実行します

再帰的

パイソン

def lowestCommonAncestor(self, root, p, q):
    next = p.val < root.val > q.val and root.left or \
           p.val > root.val < q.val and root.right
    return self.lowestCommonAncestor(next, p, q) if next else root

ジャワ

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    return (root.val - p.val) * (root.val - q.val) < 1 ? root :
           lowestCommonAncestor(p.val < root.val ? root.left : root.right, p, q);
}

score 2 · Accepted Answer

Node *LCA(Node *root, Node *p, Node *q) {
  if (!root) return NULL;
  if (root == p || root == q) return root;
  Node *L = LCA(root->left, p, q);
  Node *R = LCA(root->right, p, q);
  if (L && R) return root;  // if p and q are on both sides
  return L ? L : R;  // either one of p,q is on one side OR p,q is not in L&R subtrees
}

score 2 · Accepted Answer

スカラでは、次のことができます。

  abstract class Tree
  case class Node(a:Int, left:Tree, right:Tree) extends Tree
  case class Leaf(a:Int) extends Tree

  def lca(tree:Tree, a:Int, b:Int):Tree = {
    tree match {
      case Node(ab,l,r) => {
        if(ab==a || ab ==b) tree else {
          val temp = lca(l,a,b);
          val temp2 = lca(r,a,b);
          if(temp!=null && temp2 !=null)
            tree
          else if (temp==null && temp2==null)
            null
          else if (temp==null) r else l
        }

      }
      case Leaf(ab) => if(ab==a || ab ==b) tree else null
    }
  }

score 2 · Accepted Answer

ノード x の子が 2*x および 2*x+1 である完全なバイナリツリーである場合は、より高速な方法があります。

int get_bits(unsigned int x) {
  int high = 31;
  int low = 0,mid;
  while(high>=low) {
    mid = (high+low)/2;
    if(1<<mid==x)
      return mid+1;
    if(1<<mid<x) {
      low = mid+1;
    }
    else {
      high = mid-1;
    }
  }
  if(1<<mid>x)
    return mid;
  return mid+1;
}

unsigned int Common_Ancestor(unsigned int x,unsigned int y) {

  int xbits = get_bits(x);
  int ybits = get_bits(y);
  int diff,kbits;
  unsigned int k;
  if(xbits>ybits) {
    diff = xbits-ybits;
    x = x >> diff;
  }
  else if(xbits<ybits) {
    diff = ybits-xbits;
    y = y >> diff;
  }
  k = x^y;
  kbits = get_bits(k);
  return y>>kbits;  
}

それはどのように機能しますか

x と y を表すのに必要なビットを取得します。二分探索を使用すると、O(log(32)) になります。

x & y の 2 進表記の共通接頭辞は、共通の祖先です。

より大きなビット数で表される方は、 k >> diff によって同じビットになります

k = x^y は、x & y の共通のプレフィックスを消去します

残りのサフィックスを表すビットを見つける

x または y をサフィックスビットだけシフトして、共通の祖先である共通のプレフィックスを取得します。

これは、基本的に、両方の数値が等しくなるまで、大きい方の数値を再帰的に 2 で割るために機能します。その数が共通の祖先です。除算は、事実上、右シフト演算です。したがって、最も近い祖先を見つけるには、2 つの数字の共通の接頭辞を見つける必要があります。

score 2 · Accepted Answer

2 つのノード間の最下位の共通祖先でnode1ありnode2、両方のノードを子孫として持つツリー内の最下位のノードです。

二分木は、両方のノードが見つかるまで、ルートノードからトラバースされます。ノードにアクセスするたびに、ディクショナリに追加されます ( と呼ばれparentます)。バイナリツリーで両方のノードが見つかるとnode1、ディクショナリを使用しての祖先が取得され、セットに追加されます ( と呼ばれancestorsます)。この手順は、の場合と同じ方法で行われnode2ます。の祖先がnode2の祖先セットに存在する場合node1、それはそれらの間の最初の共通の祖先です。

以下は、スタックとディクショナリを使用して実装された反復的な python ソリューションであり、次の点があります。

ノードはそれ自体の子孫になることができます
二分木内のすべてのノードは一意です
node1二分木node2 に存在します

class Node:
    def __init__(self, data=None, left=None, right=None):
        self.data  = data
        self.left  = left
        self.right = right

def lowest_common_ancestor(root, node1, node2):
    parent = {root: None}
    stack = [root]
    
    while node1 not in parent or node2 not in parent:
        node = stack[-1]
        stack.pop()
        if node.left:
            parent[node.left] = node
            stack.append(node.left)
        if node.right:
            parent[node.right] = node
            stack.append(node.right)
    
    ancestors = set()
    while node1:
        ancestors.add(node1)
        node1 = parent[node1]
    while node2 not in ancestors:
        node2 = parent[node2]
    
    return node2.data

def main():
    '''
    Construct the below binary tree:

            30
           /  \
          /    \
         /      \
        11      29
       /  \    /  \
      8   12  25  14

    '''
    root = Node(30)
    root.left  = Node(11)
    root.right = Node(29)
    root.left.left  = Node(8)
    root.left.right = Node(12)
    root.right.left  = Node(25)
    root.right.right = Node(14)

    print(lowest_common_ancestor(root, root.left.left, root.left.right))       # 11
    print(lowest_common_ancestor(root, root.left.left, root.left))             # 11
    print(lowest_common_ancestor(root, root.left.left, root.right.right))      # 30


if __name__ == '__main__':
    main()

このアプローチの複雑さは次のとおりです。 O(n)

score 0 · Accepted Answer

最下位共通祖先を見つける最も簡単な方法は、次のアルゴリズムを使用することです。

ルートノードを調べる

value1 と value2 が厳密にルート ノードの値よりも小さい場合
    左のサブツリーを調べる
そうでなければ、value1 と value2 がルート ノードの値より厳密に大きい場合
    右側のサブツリーを調べる
そうしないと
    ルートを返す

public int LCA(TreeNode root, int value 1, int value 2) {
    while (root != null) {
       if (value1 < root.data && value2 < root.data)
           return LCA(root.left, value1, value2);
       else if (value2 > root.data && value2 2 root.data)
           return LCA(root.right, value1, value2);
       else
           return root
    }

    return null;
}

score 0 · Accepted Answer

これが私が思うことです、

最初のノードのルートを見つけて、arr1 に保存します。
2 ノードのルートの検索を開始します。その間、ルートから arr1 までのすべての値を確認します。
値が異なる場合、終了します。古い一致値が LCA です。

複雑さ : ステップ 1 : O(n) 、ステップ 2 =~ O(n) 、合計 =~ O(n)。

score 0 · Accepted Answer

解決策を見つけました

順番に取る
予約注文する
ポストオーダーを取る

3 回のトラバーサルによって、誰が LCA であるかを決定できます。LCA から、両方のノードの距離を見つけます。これら 2 つの距離を足すと、答えになります。

score 0 · Accepted Answer

疑似コード (大学の宿題用) に興味がある人は、ここに 1 つあります。

GETLCA(BINARYTREE BT, NODE A, NODE  B)
IF Root==NIL
    return NIL
ENDIF

IF Root==A OR root==B
    return Root
ENDIF

Left = GETLCA (Root.Left, A, B)
Right = GETLCA (Root.Right, A, B)

IF Left! = NIL AND Right! = NIL
    return root
ELSEIF Left! = NIL
    Return Left
ELSE
    Return Right
ENDIF

score 0 · Accepted Answer

以下は、これを解決する最速の方法です。空間複雑度 O(1) 、時間複雑度 O(n)。もしも

ノードの左と右の両方の値が null でない場合、そのノードが答えです (上から 3 番目の「if」)。値が見つかったかどうかを反復している間、すべての値は一意であり、存在する必要があるため、その子孫を検索する必要はありません。一致した見つかったノードを返すだけです。ノードの左右両方のブランチコンテンツが null の場合、null が上方に伝搬されます。トップレベルの再帰に達したとき、1 つのブランチが値を返した場合、他のブランチはその値を伝播し続けません。両方が null 以外を返した場合は、現在のノードを返します。1 つの null と別の null でないルートレベルの再帰に達した場合は、null 以外の値を返します。問題は、値が存在することを約束するため、トラバースしたことのない見つかったノードの子ツリーにある必要があります。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        if(root.val == p.val || root.val == q.val) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right !=null) return root;
        if (left == null && right ==null) return null;
        return (left != null ? left : right);
    }
}

score 0 · Accepted Answer

これはすでに回答されていますが、これがCプログラミング言語を使用したこの問題への私のアプローチです。コードは (insert() に関する限り) 二分探索木を示していますが、アルゴリズムは二分木でも機能します。アイデアは、ノード A からノード B にあるすべてのノードを順番にトラバーサルで調べ、ポストオーダートラバーサルでこれらのインデックスを検索することです。ポストオーダートラバーサルで最大のインデックスを持つノードは、最も低い共通の祖先です。

これは、バイナリツリーで共通の最下位の祖先を見つける関数を実装するための実用的な C コードです。私はすべてのユーティリティ関数なども提供していますが、簡単に理解するために CommonAncestor() にジャンプします。

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <math.h>

static inline int min (int a, int b)
{
    return ((a < b) ? a : b);
}
static inline int max (int a, int b)
{
    return ((a > b) ? a : b);
}

typedef struct node_ {
    int value;
    struct node_ * left;
    struct node_ * right;
} node;

#define MAX 12

int IN_ORDER[MAX] = {0};
int POST_ORDER[MAX] = {0};

createNode(int value) 
{
    node * temp_node = (node *)malloc(sizeof(node));
    temp_node->left = temp_node->right = NULL;
    temp_node->value = value;
    return temp_node;
}

node *
insert(node * root, int value)
{
    if (!root) {
        return createNode(value);
    }

    if (root->value > value) {
        root->left = insert(root->left, value);
    } else {
        root->right = insert(root->right, value);
    }

    return root;
}


/* Builds inorder traversal path in the IN array */
void
inorder(node * root, int * IN)
{
    static int i = 0;

    if (!root) return;

    inorder(root->left, IN);
    IN[i] = root->value;
    i++;
    inorder(root->right, IN);
}

/* Builds post traversal path in the POST array */

void
postorder (node * root, int * POST)
{
    static int i = 0;

    if (!root) return;

    postorder(root->left, POST);
    postorder(root->right, POST);
    POST[i] = root->value;
    i++;
}


int
findIndex(int * A, int value)
{
    int i = 0;
    for(i = 0; i< MAX; i++) {
        if(A[i] == value) return i;
    }
}
int
CommonAncestor(int val1, int val2)
{
    int in_val1, in_val2;
    int post_val1, post_val2;
    int j=0, i = 0; int max_index = -1;

    in_val1 = findIndex(IN_ORDER, val1);
    in_val2 = findIndex(IN_ORDER, val2);
    post_val1 = findIndex(POST_ORDER, val1);
    post_val2 = findIndex(POST_ORDER, val2);

    for (i = min(in_val1, in_val2); i<= max(in_val1, in_val2); i++) {
        for(j = 0; j < MAX; j++) {
            if (IN_ORDER[i] == POST_ORDER[j]) {
                if (j > max_index) {
                    max_index = j;
                }
            }
        }
    }
    printf("\ncommon ancestor of %d and %d is %d\n", val1, val2, POST_ORDER[max_index]);
    return max_index;
}
int main()
{
    node * root = NULL; 

    /* Build a tree with following values */
    //40, 20, 10, 30, 5, 15, 25, 35, 1, 80, 60, 100
    root = insert(root, 40);
    insert(root, 20);
    insert(root, 10);
    insert(root, 30);
    insert(root, 5);
    insert(root, 15);
    insert(root, 25);
    insert(root, 35);
    insert(root, 1);
    insert(root, 80);
    insert(root, 60);
    insert(root, 100);

    /* Get IN_ORDER traversal in the array */
    inorder(root, IN_ORDER);

    /* Get post order traversal in the array */
    postorder(root, POST_ORDER);

    CommonAncestor(1, 100);


}

score 0 · Accepted Answer

粗い方法:

すべてのノードで
- X = ノードの左側に n1、n2 のいずれかが存在するかどうかを調べる
- Y = ノードの右側に n1、n2 のいずれかが存在するかどうかを調べる
  - ノード自体が n1 || の場合 n2、一般化の目的で左または右のいずれかにあると呼ぶことができます。
- X と Y の両方が true の場合、ノードは CA です

上記の方法の問題は、「検索」を複数回行うことです。つまり、各ノードが複数回トラバースされる可能性があります。情報を再処理しないように記録できれば、この問題を克服できます (動的計画法を考えてください)。

そのため、すべてのノードを検索するのではなく、すでに見つかったものを記録します。

より良い方法：

特定のノードが left_set (n1 | n2 のいずれかが左側のサブツリーで見つかったことを意味する) であるか、深さ優先で right_set であるかを確認します。(注: n1 | n2 のいずれかである場合、ルート自体に left_set であるというプロパティを与えています)
left_set と right_set の両方の場合、ノードは LCA です。

コード：

struct Node *
findCA(struct Node *root, struct Node *n1, struct Node *n2, int *set) {
   int left_set, right_set;
   left_set = right_set = 0;
   struct Node *leftCA, *rightCA;
   leftCA = rightCA = NULL;

   if (root == NULL) {
      return NULL;
   }
   if (root == n1 || root == n2) {
      left_set = 1;
      if (n1 == n2) {
         right_set = 1;
      }
   }

   if(!left_set) {
      leftCA = findCA(root->left, n1, n2, &left_set);
      if (leftCA) {
         return leftCA;
      }
   }
   if (!right_set) {
      rightCA= findCA(root->right, n1, n2, &right_set);
      if(rightCA) {
         return rightCA;
      }
   }

   if (left_set && right_set) {
      return root;
   } else {
      *set = (left_set || right_set);
      return NULL;
   }
}

score -1 · Accepted Answer

Phpのコード。ツリーは配列バイナリツリーであると仮定しました。したがって、ツリーで LCA を計算する必要さえありません。入力: 2 つのノードのインデックス出力: LCA のインデックス

    <?php
 global $Ps;

function parents($l,$Ps)
{

    if($l % 2 ==0)
        $p = ($l-2)/2;
    else            
        $p = ($l-1)/2;

    array_push($Ps,$p);     
    if($p !=0)
        parents($p,$Ps);

    return $Ps; 
}
function lca($n,$m)
{
    $LCA = 0;
    $arr1 = array();
    $arr2 = array();
    unset($Ps); 
$Ps = array_fill(0,1,0);
    $arr1 = parents($n,$arr1);
    unset($Ps); 
$Ps = array_fill(0,1,0);
    $arr2 = parents($m,$arr2);

    if(count($arr1) > count($arr2))
        $limit = count($arr2);
    else
        $limit = count($arr1);

    for($i =0;$i<$limit;$i++)
    {
        if($arr1[$i] == $arr2[$i])
        {
            $LCA = $arr1[$i];
            break;
        }
    }
    return $LCA;//this is the index of the element in the tree

}

var_dump(lca(5,6));
?>

欠点があれば言ってください。

score -1 · Accepted Answer

//両方の値が現在のノードより小さい場合は、左側のサブツリーをトラバースします //または、両方の値が現在のノードより大きい場合は、右側のサブツリーをトラバースします //または、LCA が現在のノードです

public BSTNode findLowestCommonAncestor(BSTNode currentRoot, int a, int b){
    BSTNode commonAncestor = null;
    if (currentRoot == null) {
        System.out.println("The Tree does not exist");
        return null;
    }

    int currentNodeValue = currentRoot.getValue();
    //If both the values are less than the current node then traverse the left subtree
    //Or If both the values are greater than the current node then traverse the right subtree
    //Or LCA is the current node
    if (a < currentNodeValue && b < currentNodeValue) {
        commonAncestor = findLowestCommonAncestor(currentRoot.getLeft(), a, b);
    } else if (a > currentNodeValue && b > currentNodeValue) {
        commonAncestor = findLowestCommonAncestor(currentRoot.getRight(), a, b);
    } else {
        commonAncestor = currentRoot;
    }

    return commonAncestor;
}

score -2 · Accepted Answer

public class LeastCommonAncestor {

    private TreeNode root;

    private static class TreeNode {
        TreeNode left;
        TreeNode right;
        int item;

        TreeNode (TreeNode left, TreeNode right, int item) {
            this.left = left;
            this.right = right;
            this.item = item;
        }
    }

    public void createBinaryTree (Integer[] arr) {
        if (arr == null)  {
            throw new NullPointerException("The input array is null.");
        }

        root = new TreeNode(null, null, arr[0]);

        final Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);

        final int half = arr.length / 2;

        for (int i = 0; i < half; i++) {
            if (arr[i] != null) {
                final TreeNode current = queue.poll();
                final int left = 2 * i + 1;
                final int right = 2 * i + 2;

                if (arr[left] != null) {
                    current.left = new TreeNode(null, null, arr[left]);
                    queue.add(current.left);
                }
                if (right < arr.length && arr[right] != null) {
                    current.right = new TreeNode(null, null, arr[right]);
                    queue.add(current.right);
                }
            }
        }
    }

    private static class LCAData {
        TreeNode lca;
        int count;

        public LCAData(TreeNode parent, int count) {
            this.lca = parent;
            this.count = count;
        }
    }


    public int leastCommonAncestor(int n1, int n2) {
        if (root == null) {
            throw new NoSuchElementException("The tree is empty.");
        }

        LCAData lcaData = new LCAData(null, 0);
       // foundMatch (root, lcaData, n1,  n2);

        /**
         * QQ: boolean was returned but never used by caller.
         */
        foundMatchAndDuplicate (root, lcaData, n1,  n2, new HashSet<Integer>());

        if (lcaData.lca != null) {
            return lcaData.lca.item;
        } else {
            /**
             * QQ: Illegal thrown after processing function.
             */
            throw new IllegalArgumentException("The tree does not contain either one or more of input data. ");
        }
    }

//    /**
//     * Duplicate n1, n1         Duplicate in Tree
//     *      x                           x               => succeeds
//     *      x                           1               => fails.
//     *      1                           x               => succeeds by throwing exception
//     *      1                           1               => succeeds
//     */
//    private boolean foundMatch (TreeNode node, LCAData lcaData, int n1, int n2) {
//        if (node == null) {
//            return false;
//        }
//
//        if (lcaData.count == 2) {
//            return false;
//        }
//
//        if ((node.item == n1 || node.item == n2) && lcaData.count == 1) {
//            lcaData.count++;
//            return true;
//        }
//
//        boolean foundInCurrent = false;
//        if (node.item == n1 || node.item == n2) {
//            lcaData.count++;
//            foundInCurrent = true;
//        }
//
//        boolean foundInLeft = foundMatch(node.left, lcaData, n1, n2);
//        boolean foundInRight = foundMatch(node.right, lcaData, n1, n2);
//
//        if ((foundInLeft && foundInRight) || (foundInCurrent && foundInRight) || (foundInCurrent && foundInLeft)) {
//            lcaData.lca = node;
//            return true; 
//        }
//        return foundInCurrent || (foundInLeft || foundInRight);
//    }


    private boolean foundMatchAndDuplicate (TreeNode node, LCAData lcaData, int n1, int n2, Set<Integer> set) {
        if (node == null) {
            return false;
        }

        // when both were found
        if (lcaData.count == 2) {
            return false;
        }

        // when only one of them is found
        if ((node.item == n1 || node.item == n2) && lcaData.count == 1) {
            if (!set.contains(node.item)) {
                lcaData.count++;
                return true;
            }
        }

        boolean foundInCurrent = false;  
        // when nothing was found (count == 0), or a duplicate was found (count == 1)
        if (node.item == n1 || node.item == n2) {
            if (!set.contains(node.item)) {
                set.add(node.item);
                lcaData.count++;
            }
            foundInCurrent = true;
        }

        boolean foundInLeft = foundMatchAndDuplicate(node.left, lcaData, n1, n2, set);
        boolean foundInRight = foundMatchAndDuplicate(node.right, lcaData, n1, n2, set);

        if (((foundInLeft && foundInRight) || 
                (foundInCurrent && foundInRight) || 
                    (foundInCurrent && foundInLeft)) &&
                        lcaData.lca == null) {
            lcaData.lca = node;
            return true; 
        }
        return foundInCurrent || (foundInLeft || foundInRight);
    }




    public static void main(String args[]) {
        /**
         * Binary tree with unique values.
         */
        Integer[] arr1 = {1, 2, 3, 4, null, 6, 7, 8, null, null, null, null, 9};
        LeastCommonAncestor commonAncestor = new LeastCommonAncestor();
        commonAncestor.createBinaryTree(arr1);

        int ancestor = commonAncestor.leastCommonAncestor(2, 4);
        System.out.println("Expected 2, actual " + ancestor);

        ancestor = commonAncestor.leastCommonAncestor(2, 7);
        System.out.println("Expected 1, actual " +ancestor);

        ancestor = commonAncestor.leastCommonAncestor(2, 6);
        System.out.println("Expected 1, actual " + ancestor);

        ancestor = commonAncestor.leastCommonAncestor(2, 1);
        System.out.println("Expected 1, actual " +ancestor);

        ancestor = commonAncestor.leastCommonAncestor(3, 8);
        System.out.println("Expected 1, actual " +ancestor);

        ancestor = commonAncestor.leastCommonAncestor(7, 9);
        System.out.println("Expected 3, actual " +ancestor);

        // duplicate request 
        try {
            ancestor = commonAncestor.leastCommonAncestor(7, 7);
        } catch (Exception e) {
            System.out.println("expected exception");
        }

        /**
         * Binary tree with duplicate values.
         */
        Integer[] arr2 = {1, 2, 8, 4, null, 6, 7, 8, null, null, null, null, 9};
        commonAncestor = new LeastCommonAncestor();
        commonAncestor.createBinaryTree(arr2);

        // duplicate requested
        ancestor = commonAncestor.leastCommonAncestor(8, 8);
        System.out.println("Expected 1, actual " + ancestor);

        ancestor = commonAncestor.leastCommonAncestor(4, 8);
        System.out.println("Expected 4, actual " +ancestor);

        ancestor = commonAncestor.leastCommonAncestor(7, 8);
        System.out.println("Expected 8, actual " +ancestor);

        ancestor = commonAncestor.leastCommonAncestor(2, 6);
        System.out.println("Expected 1, actual " + ancestor);

         ancestor = commonAncestor.leastCommonAncestor(8, 9);  
        System.out.println("Expected 8, actual " +ancestor); // failed.
    }
}

algorithm - 二分木で2つのノードの最も低い共通の祖先を見つける方法は?

34 に答える 34

Related

Reference