バイナリツリー：1つのノードでLCAを実装するにはどうすればよいですか？

Question

Imは再帰を使用して今すぐ作成しようとしていますが、Imは苦労しています。論理的なエラーがあると思います。

誰かがここに私のコードはこれまでのところですT_T

私に助けてください

import java.util.ArrayList; 
    public class BTNode{ 
     private BTNode root, left,right; 
     private int item; 

    public BTNode(int item){ 
     this(item,null,null,null); 
    } 
    public BTNode(int item, BTNode left, BTNode right, BTNode root,int count){ 
     this.item = item; 
     this.left = left; 
     this.right = right; 
     this.root = root; 
     this.count=count; 
    } 
    public void build(){ 
     this.left = new BTNode(40); 
     this.left.root = this; 

     this.right = new BTNode(100); 
     this.right.root = this; 

     this.left.right = new BTNode(45); 
     this.left.right.root = this.left; 

     this.left.left = new BTNode(25); 
     this.left.left.root = this.left; 

     this.right.left = new BTNode(70); 
     this.right.left.root = this.right; 

     this.right.right = new BTNode(200); 
     this.right.right.root = this.right; 

    } 
    public void inorder(){//recursion 
     //traverse the left 
     if(left != null) 
      left.inorder(); 
     //visit the root do the item 
     System.out.print(this.item+" "); 
     //traverse the right 
     if(right != null) 
      right.inorder(); 
    } 
    public String inToString(){ 
     return ((left == null)?"": left.inToString()) + item + " " + ((right == null)?"": right.inToString()+" "); 
    } 
    //preorder() 
    public void preorder(){ 

     //visit the root do the item 
     System.out.print(this.item+" "); 
     //traverse the left 
     if(left != null) 
      left.preorder(); 
     //traverse the right 
     if(right != null) 
      right.preorder(); 
    } 
    //preToString() 
    public String preToString(){ 
     return item+ " "+((left == null)?"": left.preToString())+ ((right == null)?"": right.preToString()+" "); 
    } 
    //postorder() 
    public void postorder(){ 
     //traverse the left 
     if(left != null) 
      left.postorder(); 
     //traverse the right 
     if(right != null) 
      right.postorder(); 
     //visit root do the item 
     System.out.print(this.item+" "); 

    } 
    //postToString() 
    public String postToString(){ 
     return ((left == null)?"": left.postToString()) + ((right == null)?"": right.postToString()+" ")+item+ " "; 
    } 



    //findsum-recursive 
    public int findsum(){ 
     //traverse left,if null traverse to right then add the two item lastly add to the root 
     return ((left == null)?0: left.findsum()) + ((right == null)?0: right.findsum())+item; 
    } 




    //findlevel-recursive 
    public int findlevel(){ 
     //check left && right if it is not null then iterate method recursively 
     if (left == null) 
       return 0; 
     else if(right == null) 
      return 0; 
     else 
      return 1 + left.findlevel(); 
    } 
    /* 
    //ancestor-recursive 
    public BTNode ancestor(int value){ 
     if(left.count== 2){//check the root 
     return left.ancestor();//traverse left node 
     } 
     System.out.print(item+" ");//print item if the left turns false 
     if(root != null){ 
     right.ancestor();//traverse right node 
     } 
    }*/ 



    public int count(){ 
     //check if left || right are null then return 0, otherwise method were recursively executed 
     return (((left==null)?0:1+left.count())+((right==null)?0:1+right.count())); 
    } 

    public void reference(){ 
     //check left != null print the root, traverse left, traverse right 
     if(left != null) 
     left.reference(); 
     if(left != null) 
     System.out.print(item+" "); 
     if(right != null) 
     right.reference(); 

    } 
    public void sort(){ 

    } 
    public void insert(int given){ 
     BTNode node = new BTNode(given); 

     if(item == 0) 
     root = node; 
     else 
     { 
      BTNode current = root; //points to the current Node 
      BTNode parent; //points to the parent Node 

      while(current != null) 
      { 
       if(item > given) 
       { 
        parent = current; 
        current = left; 
       } 

       if(item < given) 
       { 
        parent = current; 
        current = right; 
       } 
      } 
      current = node; 
      if(item < given) 
       right = node; 
      else 
       left = node; 
     } 
     right.inorder(); 
    } 
    public boolean contains(int given){ 
     return ((left==null)?false:left.contains(given))|| item==given || ((right == null)?false : right.contains(given)); 
     /*if(left != null) 
      left.contains(given); 
     if(right != null) 
      right.contains(given); 
     return item == given;*/ 
    } 
    public static void main(String[]args){ 
     BTNode root = new BTNode(50); 

     root.build(); 
     System.out.print("\nGiven :"+root.inToString()); 
     System.out.println("\ninorder"); 
     root.inorder(); 
     System.out.println("\npreorder"); 
     root.preorder(); 
     System.out.println("\npostorder"); 
     root.postorder(); 
     System.out.println("\nfindsum"); 
     System.out.println(root.findsum()); 
     System.out.println("\nfindlevel"); 
     //System.out.println(root.findlevel(200)); 
     System.out.println(root.findlevel()); 
     System.out.println("\nancestor"); 
     //System.out.println(root.ancestor()); 
     root.ancestor(); 
     System.out.println("\ncount"); 
     System.out.println(root.count()); 

     System.out.println("\nreference"); 
     //System.out.println(root.reference()); 
     root.reference(); 
     System.out.println("\nsort"); 
     //System.out.print(root.sort()); 
     root.sort(); 
     System.out.println("\nContains"); 
     System.out.println(root.contains(new Integer(70))); 
     System.out.println("\ninsert"); 
     //System.out.print(root.sort()); 
     root.insert(new Integer(71)); 
      root.printinorder(); 
    } 
} 

も...私はそれを

Answer 1

を行うための正しい方法であると思ういけない私の挿入機構を確認してくださいあなたの質問が不明なので、あなたの潜在的な質問の両方に答えています。

1-ノードの最小祖先を探したい場合は、これまでに見つかった最小の親値のトラックを維持しながら、ノードkeepがその親を越えて移動することができます。ルートノードに到達すると、最小の値になります。このアルゴリズムの時間複雑度はO（h）であり、ここでhは木の高さである。これは非常に簡単なので、ここでコードサンプルを提供していません。

2 LCA（あなたのタイトルが何であるか）を探したい場合は、非常に似たようなことができます。キーn1とn2がバイナリツリーに存在すると仮定すると、バイナリツリーの単一トラバーサルとパス配列のための余分なストレージなしでLCAを見つけることができます。アイデアはルートから始まるツリーを横断することです。指定されたキー（n1とn2）のいずれかがルートと一致する場合、ルートはLCAです（両方のキーが存在すると仮定します）。ルートがいずれのキーとも一致しない場合、左右のサブツリーに対して繰り返されます。左のサブツリーに1つのキーが存在し、右のサブツリーに存在する他のキーがLCAです。両方のキーが左のサブツリーにある場合、左のサブツリーにもLCAがあり、そうでない場合はLCAが右のサブツリーにあります。ここでは、（このコードは動作します）あなたの必要性に応じて調整することができますサンプルコードです：

//Java implementation to find lowest common ancestor of 
// n1 and n2 using one traversal of binary tree 

/* Class containing left and right child of current 
node and key value*/ 
class Node 
{ 
    int data; 
    Node left, right; 

    public Node(int item) 
    { 
     data = item; 
     left = right = null; 
    } 
} 

public class BinaryTree 
{ 
    //Root of the Binary Tree 
    Node root; 

    Node findLCA(int n1, int n2) 
    { 
     return findLCA(root, n1, n2); 
    } 

    // This function returns pointer to LCA of two given 
    // values n1 and n2. This function assumes that n1 and 
    // n2 are present in Binary Tree 
    Node findLCA(Node node, int n1, int n2) 
    { 
     // Base case 
     if (node == null) 
      return null; 

     // If either n1 or n2 matches with root's key, report 
     // the presence by returning root (Note that if a key is 
     // ancestor of other, then the ancestor key becomes LCA 
     if (node.data == n1 || node.data == n2) 
      return node; 

     // Look for keys in left and right subtrees 
     Node left_lca = findLCA(node.left, n1, n2); 
     Node right_lca = findLCA(node.right, n1, n2); 

     // If both of the above calls return Non-NULL, then one key 
     // is present in once subtree and other is present in other, 
     // So this node is the LCA 
     if (left_lca!=null && right_lca!=null) 
      return node; 

     // Otherwise check if left subtree or right subtree is LCA 
     return (left_lca != null) ? left_lca : right_lca; 
    } 

    /* Driver program to test above functions */ 
    public static void main(String args[]) 
    { 
     BinaryTree tree = new BinaryTree(); 
     tree.root = new Node(1); 
     tree.root.left = new Node(2); 
     tree.root.right = new Node(3); 
     tree.root.left.left = new Node(4); 
     tree.root.left.right = new Node(5); 
     tree.root.right.left = new Node(6); 
     tree.root.right.right = new Node(7); 
     System.out.println("LCA(4, 5) = " + 
          tree.findLCA(4, 5).data); 
     System.out.println("LCA(4, 6) = " + 
          tree.findLCA(4, 6).data); 
     System.out.println("LCA(3, 4) = " + 
          tree.findLCA(3, 4).data); 
     System.out.println("LCA(2, 4) = " + 
          tree.findLCA(2, 4).data); 
    } 
} 

この方法およびコードはあなたにも、オンラインIDEでコードを実行することができます。このサイトでhttp://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/からのものです。