如果在每个根到叶的路径中，相邻两个关键点之间的绝对差为1，则树是连续树。如果给我们一棵二叉树，我们需要检查这棵树是否是连续的。
null
例如：
Input : 3 / 2 4 / 1 3 5Output: "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 1Input : 7 / 5 8 / 6 4 10Output: "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<bits/stdc++.h> 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 |
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（队列））
说明：
我们只需逐级遍历每个节点，并检查父节点和子节点之间的差异是否为1，如果所有节点都为真，那么我们将返回 符合事实的 否则我们会回来的 错误的 .
C++14
// CPP Code to check if the tree is continuous or not #include <bits/stdc++.h> 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" ; else cout << "False" ; 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( "True" ); else System.out.print( "False" ); } } // This code is contributed by Rajput-Ji |
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( "True" ); else Console.Write( "False" ); } } // 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<br>" ); else document.write( "False<br>" ); // This code is contributed by avanitrachhadiya2155 </script> |
输出
True
时间复杂性： O（n）
如果你喜欢Geeksforgek，并且想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
