Wie kann ich Java iterativen Code für die Überprüfung schreiben, zwei Bäume sind identisch oder nicht?

Question

Ich habe rekursive Lösung für identische Bäume zu überprüfen gefunden. aber ich möchte iterative Lösung. Kann jemand erklären, wie man für dieses Problem iterativ in Java programmiert?

Answer 1

Sie können die Überprüfung der Ebenenreihenfolge verwenden. Sie benötigen zwei Warteschlangen.

Algorithmus:

isIdentical(tree1, tree2) 

1.If both trees are empty then return true, if either one is empty then return false. 
2.take 2 queues and push first node of tree1 into q1 and first node of tree2 into q2. 
3.while(q1.size()>0 && q2.size()>0) 
    take first node of both the queues, say n1 and n2; 
    (a) if n1(data)==n2(data) OR both have left and right child or noone have or both have any of child then return true 
    (b) else if child's data are different then return false 
    (c) if n1 or n2 have left or right child then add it to it's respective queue. 
4. if size of both quques are different then return false 
5. return true 

-Code in Java (Lauf komplett):

import java.util.*; 

class Node { 

    int data; 
    Node right, left; 

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

class Tree { 

    Node root; 

    Tree() { 
     root = null; 
    } 

    public boolean isIdentical(Node r1, Node r2) { 
     if (r1 == null && r2 == null) { 
      return true; 
     } 
     if ((r1 != null && r2 == null) || (r1 == null && r2 != null)) { 
      return false; 
     } 
     Queue q1 = new LinkedList(); 
     Queue q2 = new LinkedList(); 
     q1.add(r1); 
     q2.add(r2); 
     while (q1.size() > 0 && q2.size() > 0) { 
      Node n1 = (Node) q1.poll(); 
      Node n2 = (Node) q2.poll(); 
      if (n1.data != n2.data || (n1.left != null && n2.left == null) || (n1.right != null && n2.right == null) 
        || (n1.left == null && n2.left != null) || (n1.right == null && n2.right != null)) { 
       return false; 
      } else if (n1.left.data != n2.left.data || n1.right.data != n2.right.data) { 
       return false; 
      } 
      if (n1.left != null) { 
       q1.add(n1.left); 
      } 
      if (n1.right != null) { 
       q1.add(n1.right); 
      } 
      if (n2.left != null) { 
       q2.add(n1.left); 
      } 
      if (n2.right != null) { 
       q2.add(n1.right); 
      } 
      return true; 
     } 
     if (q1.size() != q2.size()) { 
      return false; 
     } 
     return true; 
    } 
} 

public class Test { 

    public static void main(String[] args) { 
     Tree t = new Tree(); 
     Tree u = new Tree(); 
     t.root = new Node(10); 
     t.root.left = new Node(15); 
     t.root.right = new Node(20); 

     u.root = new Node(10); 
     u.root.left = new Node(15); 
     u.root.right = new Node(20); 

     if (t.isIdentical(t.root, u.root)) { 
      System.out.println("Identical"); 
     } else { 
      System.out.println("not Identical"); 
     } 
    } 
}