1

least common Ancestorで 2 つnodesのを見つけるためのこのコードがありますbinary tree。時間計算量は だと思いますO(log n)。しかし、専門家の意見が必要です。このコードは私の入力ではかなりうまく機能しますが、徹底的にテストしたかどうかはわかりません。

ここにコードがあります

//LCA of Binary tree
        public static Node LCABT(Node root, int v1, int v2){
            if (root==null)
                return null;
            if (root.data==v1 || root.data==v2){
                return root;
            }
            Node left = LCABT(root.left,v1,v2);
            Node right = LCABT(root.right,v1,v2);

            if(left!=null && right!=null)
                return root;
            else if (left!=null)
                 return left;
            else  return right;
        }
4

2 に答える 2

2

O(n)ツリー全体をトラバースしているため、つまり、そのすべてのノードにアクセスしているため、コードの時間計算量はです。ただし、BST がなく、バイナリ ツリーのみの場合は、親ノードにポインターを持たずに達成できる最善の方法です (その場合、両方のノードからルート ノードへのパスを構築し、次のノードを返します)。両方のパスで)。BST がある場合は、両方のノードを見つけて で最小共通祖先を見つけることができますO(h)。ここで、h はツリーの高さであり、ツリーのO(log n)バランスがとれている場合です。

最後に - コンテストや面接の準備をしている場合は、特殊なケースに注意してください。コードは、ノードの 1 つがツリーに含まれていない場合を処理しません。

于 2014-01-29T07:59:29.750 に答える