Arbore continuu
Un arbore este un arbore continuu dacă în fiecare cale de la rădăcină la frunză diferența absolută dintre cheile a două adiacente este 1. Ni se dă un arbore binar, trebuie să verificăm dacă arborele este continuu sau nu.
Exemple:
Input : 3 / 2 4 / 1 3 5 Output: 'Yes' // 3->2->1 every two adjacent node's absolute difference is 1 // 3->2->3 every two adjacent node's absolute difference is 1 // 3->4->5 every two adjacent node's absolute difference is 1 Input : 7 / 5 8 / 6 4 10 Output: 'No' // 7->5->6 here absolute difference of 7 and 5 is not 1. // 7->5->4 here absolute difference of 7 and 5 is not 1. // 7->8->10 here absolute difference of 8 and 10 is not 1.
Soluția necesită o traversare a arborelui. Lucrurile importante de verificat sunt să vă asigurați că toate carcasele de colț sunt manipulate. Cazurile de colț includ un arbore gol cu un singur nod, un nod cu doar copilul stâng și un nod cu singurul copil drept.
În traversarea arborilor verificăm recursiv dacă subarborele stânga și dreapta sunt continue. De asemenea, verificăm dacă diferența dintre cheile cheii nodului curent și cheile sale secundare este 1. Mai jos este implementarea ideii.
Implementare:
C++ // C++ program to check if a tree is continuous or not #include using namespace std ; /* A binary tree node has data pointer to left child and a pointer to right child */ struct Node { int data ; struct Node * left * right ; }; /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ struct Node * newNode ( int data ) { struct Node * node = new Node ; node -> data = data ; node -> left = node -> right = NULL ; return ( node ); } // Function to check tree is continuous or not bool treeContinuous ( struct Node * ptr ) { // if next node is empty then return true if ( ptr == NULL ) return true ; // if current node is leaf node then return true // because it is end of root to leaf path if ( ptr -> left == NULL && ptr -> right == NULL ) return true ; // If left subtree is empty then only check right if ( ptr -> left == NULL ) return ( abs ( ptr -> data - ptr -> right -> data ) == 1 ) && treeContinuous ( ptr -> right ); // If right subtree is empty then only check left if ( ptr -> right == NULL ) return ( abs ( ptr -> data - ptr -> left -> data ) == 1 ) && treeContinuous ( ptr -> left ); // If both left and right subtrees are not empty check // everything return abs ( ptr -> data - ptr -> left -> data ) == 1 && abs ( ptr -> data - ptr -> right -> data ) == 1 && treeContinuous ( ptr -> left ) && treeContinuous ( ptr -> right ); } /* Driver program to test mirror() */ int main () { struct Node * root = newNode ( 3 ); root -> left = newNode ( 2 ); root -> right = newNode ( 4 ); root -> left -> left = newNode ( 1 ); root -> left -> right = newNode ( 3 ); root -> right -> right = newNode ( 5 ); treeContinuous ( root ) ? cout < < 'Yes' : cout < < 'No' ; return 0 ; }
Java // Java program to check if a tree is continuous or not import java.util.* ; class solution { /* A binary tree node has data pointer to left child and a pointer to right child */ static class Node { int data ; Node left right ; }; /* Helper function that allocates a new node with the given data and null left and right pointers. */ static Node newNode ( int data ) { Node node = new Node (); node . data = data ; node . left = node . right = null ; return ( node ); } // Function to check tree is continuous or not static boolean treeContinuous ( Node ptr ) { // if next node is empty then return true if ( ptr == null ) return true ; // if current node is leaf node then return true // because it is end of root to leaf path if ( ptr . left == null && ptr . right == null ) return true ; // If left subtree is empty then only check right if ( ptr . left == null ) return ( Math . abs ( ptr . data - ptr . right . data ) == 1 ) && treeContinuous ( ptr . right ); // If right subtree is empty then only check left if ( ptr . right == null ) return ( Math . abs ( ptr . data - ptr . left . data ) == 1 ) && treeContinuous ( ptr . left ); // If both left and right subtrees are not empty check // everything return Math . abs ( ptr . data - ptr . left . data ) == 1 && Math . abs ( ptr . data - ptr . right . data ) == 1 && treeContinuous ( ptr . left ) && treeContinuous ( ptr . right ); } /* Driver program to test mirror() */ public static void main ( String args [] ) { Node root = newNode ( 3 ); root . left = newNode ( 2 ); root . right = newNode ( 4 ); root . left . left = newNode ( 1 ); root . left . right = newNode ( 3 ); root . right . right = newNode ( 5 ); if ( treeContinuous ( root )) System . out . println ( 'Yes' ) ; else System . out . println ( 'No' ); } } //contributed by Arnab Kundu
Python #Python Program to check continuous tree or not # A binary tree node has data pointer to left child # an a pointer to right child */ # Helper function that allocates a new node with the # given data and null left and right pointers class newNode (): def __init__ ( self key ) : self . left = None self . right = None self . data = key # Function to check tree is continuous or not def treeContinuous ( root ): # if next node is empty then return true if not root : return True # if current node is leaf node then return true # because it is end of root to leaf path if root . left : if not abs ( root . data - root . left . data ) == 1 : return False # If right subtree is empty then only check left if root . right : if not abs ( root . data - root . right . data ) == 1 : return False # If both left and right subtrees are not empty check # everything if treeContinuous ( root . left ) and treeContinuous ( root . right ): return True # Driver code if __name__ == '__main__' : root = newNode ( 7 ) root . left = newNode ( 6 ) root . right = newNode ( 8 ) root . left . left = newNode ( 5 ) root . left . right = newNode ( 7 ) root . right . right = newNode ( 7 ) print ( treeContinuous ( root ))
C# // C# program to check if a tree is continuous or not using System ; class solution { /* A binary tree node has data pointer to left child and a pointer to right child */ class Node { public int data ; public Node left right ; }; /* Helper function that allocates a new node with the given data and null left and right pointers. */ static Node newNode ( int data ) { Node node = new Node (); node . data = data ; node . left = node . right = null ; return ( node ); } // Function to check tree is continuous or not static Boolean treeContinuous ( Node ptr ) { // if next node is empty then return true if ( ptr == null ) return true ; // if current node is leaf node then return true // because it is end of root to leaf path if ( ptr . left == null && ptr . right == null ) return true ; // If left subtree is empty then only check right if ( ptr . left == null ) return ( Math . Abs ( ptr . data - ptr . right . data ) == 1 ) && treeContinuous ( ptr . right ); // If right subtree is empty then only check left if ( ptr . right == null ) return ( Math . Abs ( ptr . data - ptr . left . data ) == 1 ) && treeContinuous ( ptr . left ); // If both left and right subtrees are not empty check // everything return Math . Abs ( ptr . data - ptr . left . data ) == 1 && Math . Abs ( ptr . data - ptr . right . data ) == 1 && treeContinuous ( ptr . left ) && treeContinuous ( ptr . right ); } /* Driver program to test mirror() */ static public void Main ( String [] args ) { Node root = newNode ( 3 ); root . left = newNode ( 2 ); root . right = newNode ( 4 ); root . left . left = newNode ( 1 ); root . left . right = newNode ( 3 ); root . right . right = newNode ( 5 ); if ( treeContinuous ( root )) Console . WriteLine ( 'Yes' ) ; else Console . WriteLine ( 'No' ); } } //contributed by Arnab Kundu
JavaScript < script > // JavaScript program to check if a tree is continuous or not /* A binary tree node has data pointer to left child and a pointer to right child */ class Node { constructor () { this . data = 0 ; this . left = null ; this . right = null ; } }; /* Helper function that allocates a new node with the given data and null left and right pointers. */ function newNode ( data ) { var node = new Node (); node . data = data ; node . left = node . right = null ; return ( node ); } // Function to check tree is continuous or not function treeContinuous ( ptr ) { // if next node is empty then return true if ( ptr == null ) return true ; // if current node is leaf node then return true // because it is end of root to leaf path if ( ptr . left == null && ptr . right == null ) return true ; // If left subtree is empty then only check right if ( ptr . left == null ) return ( Math . abs ( ptr . data - ptr . right . data ) == 1 ) && treeContinuous ( ptr . right ); // If right subtree is empty then only check left if ( ptr . right == null ) return ( Math . abs ( ptr . data - ptr . left . data ) == 1 ) && treeContinuous ( ptr . left ); // If both left and right subtrees are not empty check // everything return Math . abs ( ptr . data - ptr . left . data ) == 1 && Math . abs ( ptr . data - ptr . right . data ) == 1 && treeContinuous ( ptr . left ) && treeContinuous ( ptr . right ); } /* Driver program to test mirror() */ var root = newNode ( 3 ); root . left = newNode ( 2 ); root . right = newNode ( 4 ); root . left . left = newNode ( 1 ); root . left . right = newNode ( 3 ); root . right . right = newNode ( 5 ); if ( treeContinuous ( root )) document . write ( 'Yes' ) ; else document . write ( 'No' ); < /script>
Ieșire
Yes
O altă abordare (folosind BFS(Queue))
Explicaţie: Pur și simplu vom parcurge fiecare nod nivel cu nivel și vom verifica dacă diferența dintre părinte și copil este 1 dacă este adevărată pentru toate nodurile, atunci vom reveni adevărat altfel ne vom întoarce fals .
Implementare:
C++14 // CPP Code to check if the tree is continuous or not #include using namespace std ; // Node structure struct node { int val ; node * left ; node * right ; node () : val ( 0 ) left ( nullptr ) right ( nullptr ) { } node ( int x ) : val ( x ) left ( nullptr ) right ( nullptr ) { } node ( int x node * left node * right ) : val ( x ) left ( left ) right ( right ) { } }; // Function to check if the tree is continuous or not bool continuous ( struct node * root ) { // If root is Null then tree isn't Continuous if ( root == NULL ) return false ; int flag = 1 ; queue < struct node *> Q ; Q . push ( root ); node * temp ; // BFS Traversal while ( ! Q . empty ()) { temp = Q . front (); Q . pop (); // Move to left child if ( temp -> left ) { // if difference between parent and child is // equal to 1 then do continue otherwise make // flag = 0 and break if ( abs ( temp -> left -> val - temp -> val ) == 1 ) Q . push ( temp -> left ); else { flag = 0 ; break ; } } // Move to right child if ( temp -> right ) { // if difference between parent and child is // equal to 1 then do continue otherwise make // flag = 0 and break if ( abs ( temp -> right -> val - temp -> val ) == 1 ) Q . push ( temp -> right ); else { flag = 0 ; break ; } } } if ( flag ) return true ; else return false ; } // Driver Code int main () { // Constructing the Tree struct node * root = new node ( 3 ); root -> left = new node ( 2 ); root -> right = new node ( 4 ); root -> left -> left = new node ( 1 ); root -> left -> right = new node ( 3 ); root -> right -> right = new node ( 5 ); // Function Call if ( continuous ( root )) cout < < 'True n ' ; else cout < < 'False n ' ; return 0 ; } // This code is contributed by Sanjeev Yadav.
Java // JAVA Code to check if the tree is continuous or not import java.util.* ; class GFG { // Node structure static class node { int val ; node left ; node right ; node () { this . val = 0 ; this . left = null ; this . right = null ; } node ( int x ) { this . val = x ; this . left = null ; this . right = null ; } node ( int x node left node right ) { this . val = x ; this . left = left ; this . right = right ; } }; // Function to check if the tree is continuous or not static boolean continuous ( node root ) { // If root is Null then tree isn't Continuous if ( root == null ) return false ; int flag = 1 ; Queue < node > Q = new LinkedList <> (); Q . add ( root ); node temp ; // BFS Traversal while ( ! Q . isEmpty ()) { temp = Q . peek (); Q . remove (); // Move to left child if ( temp . left != null ) { // if difference between parent and child is // equal to 1 then do continue otherwise make // flag = 0 and break if ( Math . abs ( temp . left . val - temp . val ) == 1 ) Q . add ( temp . left ); else { flag = 0 ; break ; } } // Move to right child if ( temp . right != null ) { // if difference between parent and child is // equal to 1 then do continue otherwise make // flag = 0 and break if ( Math . abs ( temp . right . val - temp . val ) == 1 ) Q . add ( temp . right ); else { flag = 0 ; break ; } } } if ( flag != 0 ) return true ; else return false ; } // Driver Code public static void main ( String [] args ) { // Constructing the Tree node root = new node ( 3 ); root . left = new node ( 2 ); root . right = new node ( 4 ); root . left . left = new node ( 1 ); root . left . right = new node ( 3 ); root . right . right = new node ( 5 ); // Function Call if ( continuous ( root )) System . out . print ( 'Truen' ); else System . out . print ( 'Falsen' ); } } // This code is contributed by Rajput-Ji
Python3 # Python program for the above approach # Node structure class Node : def __init__ ( self x ): self . val = x self . left = None self . right = None # Function to check if the tree is continuous or not def continuous ( root ): # If root is None then tree isn't Continuous if root is None : return False flag = 1 Q = [] Q . append ( root ) temp = None # BFS Traversal while len ( Q ) != 0 : temp = Q . pop ( 0 ) # Move to left child if temp . left is not None : # if difference between parent and child is # equal to 1 then do continue otherwise make # flag = 0 and break if abs ( temp . left . val - temp . val ) == 1 : Q . append ( temp . left ) else : flag = 0 break # Move to right child if temp . right is not None : # if difference between parent and child is # equal to 1 then do continue otherwise make # flag = 0 and break if abs ( temp . right . val - temp . val ) == 1 : Q . append ( temp . right ) else : flag = 0 break if flag != 0 : return True else : return False # Driver Code # Constructing the Tree root = Node ( 3 ) root . left = Node ( 2 ) root . right = Node ( 4 ) root . left . left = Node ( 1 ) root . left . right = Node ( 3 ) root . right . right = Node ( 5 ) # Function Call if continuous ( root ): print ( 'True' ) else : print ( 'False' ) # This code is contributed by codebraxnzt
C# // C# Code to check if the tree is continuous or not using System ; using System.Collections.Generic ; class GFG { // Node structure public class node { public int val ; public node left ; public node right ; public node () { this . val = 0 ; this . left = null ; this . right = null ; } public node ( int x ) { this . val = x ; this . left = null ; this . right = null ; } public node ( int x node left node right ) { this . val = x ; this . left = left ; this . right = right ; } }; // Function to check if the tree is continuous or not static bool continuous ( node root ) { // If root is Null then tree isn't Continuous if ( root == null ) return false ; int flag = 1 ; Queue < node > Q = new Queue < node > (); Q . Enqueue ( root ); node temp ; // BFS Traversal while ( Q . Count != 0 ) { temp = Q . Peek (); Q . Dequeue (); // Move to left child if ( temp . left != null ) { // if difference between parent and child is // equal to 1 then do continue otherwise make // flag = 0 and break if ( Math . Abs ( temp . left . val - temp . val ) == 1 ) Q . Enqueue ( temp . left ); else { flag = 0 ; break ; } } // Move to right child if ( temp . right != null ) { // if difference between parent and child is // equal to 1 then do continue otherwise make // flag = 0 and break if ( Math . Abs ( temp . right . val - temp . val ) == 1 ) Q . Enqueue ( temp . right ); else { flag = 0 ; break ; } } } if ( flag != 0 ) return true ; else return false ; } // Driver Code public static void Main ( String [] args ) { // Constructing the Tree node root = new node ( 3 ); root . left = new node ( 2 ); root . right = new node ( 4 ); root . left . left = new node ( 1 ); root . left . right = new node ( 3 ); root . right . right = new node ( 5 ); // Function Call if ( continuous ( root )) Console . Write ( 'Truen' ); else Console . Write ( 'Falsen' ); } } // This code is contributed by Rajput-Ji
JavaScript < script > // Javascript Code to check if the tree is continuous or not // Node structure class Node { constructor ( x ) { this . val = x ; this . left = null ; this . right = null ; } } // Function to check if the tree is continuous or not function continuous ( root ) { // If root is Null then tree isn't Continuous if ( root == null ) return false ; let flag = 1 ; let Q = []; Q . push ( root ); let temp ; // BFS Traversal while ( Q . length != 0 ) { temp = Q . shift (); // Move to left child if ( temp . left != null ) { // if difference between parent and child is // equal to 1 then do continue otherwise make // flag = 0 and break if ( Math . abs ( temp . left . val - temp . val ) == 1 ) Q . push ( temp . left ); else { flag = 0 ; break ; } } // Move to right child if ( temp . right != null ) { // if difference between parent and child is // equal to 1 then do continue otherwise make // flag = 0 and break if ( Math . abs ( temp . right . val - temp . val ) == 1 ) Q . push ( temp . right ); else { flag = 0 ; break ; } } } if ( flag != 0 ) return true ; else return false ; } // Driver Code // Constructing the Tree let root = new Node ( 3 ); root . left = new Node ( 2 ); root . right = new Node ( 4 ); root . left . left = new Node ( 1 ); root . left . right = new Node ( 3 ); root . right . right = new Node ( 5 ); // Function Call if ( continuous ( root )) document . write ( 'True
' ); else document . write ( 'False
' ); // This code is contributed by avanitrachhadiya2155 < /script>
Ieșire
True
Complexitatea timpului: O(n)
Spațiu auxiliar: O(N) Aici N este numărul de noduri din arbore.
Creați un test
