連続ツリー
ルートからリーフへの各パスにおいて、隣接する 2 つのキー間の絶対差が 1 である場合、ツリーは連続ツリーです。ツリーが連続であるかどうかを確認する必要がある 2 分ツリーが与えられました。
例:
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.
この解決策にはツリーの走査が必要です。チェックすべき重要な点は、すべての特殊なケースが確実に処理されていることを確認することです。特殊なケースには、空のツリーの単一ノード ツリー、左側の子のみを持つノードと右側の子だけを持つノードが含まれます。
ツリートラバーサルでは、左右のサブツリーが連続しているかどうかを再帰的にチェックします。また、現在のノードのキーとその子のキーの差が 1 であるかどうかも確認します。以下は、このアイデアの実装です。
実装：
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>
出力
Yes
別のアプローチ (BFS(Queue) を使用)
説明： 各ノードをレベルごとにたどって、親と子の違いが 1 であるかどうかを確認し、それがすべてのノードで true である場合は、次の値を返します。 真実 そうでなければ戻ります 間違い 。
実装：
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>
出力
True
時間計算量: O(n)
補助スペース：O(N) ここ N はツリー内のノードの数です。
クイズの作成
