给定BST的前序遍历，检查每个非叶节点是否只有一个子节点。假设BST包含唯一的条目。
null
例子
Input: pre[] = {20, 10, 11, 13, 12}Output: YesThe given array represents following BST. In the following BST, every internalnode has exactly 1 child. Therefore, the output is true. 20 / 10 11 13 / 12
在前序遍历中，每个节点的子代（或前序后继者）出现在节点之后。在上面的示例中，20是前序中的第一个节点，20的所有子节点都出现在它之后。20的后代都比它小。对于10，所有的后代都比它更伟大。一般来说，我们可以说，如果所有内部节点在BST中只有一个子节点，那么每个节点的所有子节点都比该节点小或大。原因很简单，因为树是BST，每个节点只有一个子节点，所以一个节点的所有子节点要么在左侧，要么在右侧，这意味着所有子节点要么更小，要么更大。
方法1（天真） 这种方法简单地遵循了上面的想法，即右侧的所有值要么更小，要么更大。使用两个循环，外部循环从最左边的元素开始逐个拾取一个元素。内部循环检查拾取的元素右侧的所有元素是否都较小或较大。该方法的时间复杂度为O（n^2）。
方法2 因为一个节点的所有子节点必须大于或小于该节点。我们可以对循环中的每个节点执行以下操作。 1.查找节点的下一个前序后继者（或后代）。 2.查找节点的最后一个预排序后继者（pre[]中的最后一个元素）。 3.如果两个后继节点都小于当前节点，或者两个后继节点都大于当前节点，则继续。否则，返回false。
C++
#include<bits/stdc++.h> using namespace std; bool hasOnlyOneChild( int pre[], int size) { int nextDiff, lastDiff; for ( int i=0; i<size-1; i++) { nextDiff = pre[i] - pre[i+1]; lastDiff = pre[i] - pre[size-1]; if (nextDiff*lastDiff < 0) return false ;; } return true ; } // driver program to test above function int main() { int pre[] = {8, 3, 5, 7, 6}; int size = sizeof (pre)/ sizeof (pre[0]); if (hasOnlyOneChild(pre, size) == true ) cout<< "Yes" ; else cout<< "No" ; return 0; } // This code is contributed by rrrtnx. |
C
#include <stdio.h> bool hasOnlyOneChild( int pre[], int size) { int nextDiff, lastDiff; for ( int i=0; i<size-1; i++) { nextDiff = pre[i] - pre[i+1]; lastDiff = pre[i] - pre[size-1]; if (nextDiff*lastDiff < 0) return false ;; } return true ; } // driver program to test above function int main() { int pre[] = {8, 3, 5, 7, 6}; int size = sizeof (pre)/ sizeof (pre[0]); if (hasOnlyOneChild(pre, size) == true ) printf ( "Yes" ); else printf ( "No" ); return 0; } |
JAVA
// Check if each internal node of BST has only one child class BinaryTree { boolean hasOnlyOneChild( int pre[], int size) { int nextDiff, lastDiff; for ( int i = 0 ; i < size - 1 ; i++) { nextDiff = pre[i] - pre[i + 1 ]; lastDiff = pre[i] - pre[size - 1 ]; if (nextDiff * lastDiff < 0 ) { return false ; }; } return true ; } public static void main(String[] args) { BinaryTree tree = new BinaryTree(); int pre[] = new int []{ 8 , 3 , 5 , 7 , 6 }; int size = pre.length; if (tree.hasOnlyOneChild(pre, size) == true ) { System.out.println( "Yes" ); } else { System.out.println( "No" ); } } } // This code has been contributed by Mayank Jaiswal |
Python3
# Check if each internal # node of BST has only one child def hasOnlyOneChild (pre, size): nextDiff = 0 ; lastDiff = 0 for i in range (size - 1 ): nextDiff = pre[i] - pre[i + 1 ] lastDiff = pre[i] - pre[size - 1 ] if nextDiff * lastDiff < 0 : return False return True # driver program to # test above function if __name__ = = "__main__" : pre = [ 8 , 3 , 5 , 7 , 6 ] size = len (pre) if (hasOnlyOneChild(pre,size) = = True ): print ( "Yes" ) else : print ( "No" ) # This code is contributed by # Harshit Saini |
C#
// Check if each internal node of BST has only one child using System; public class BinaryTree { bool hasOnlyOneChild( int [] pre, int size) { int nextDiff, lastDiff; for ( int i = 0; i < size - 1; i++) { nextDiff = pre[i] - pre[i + 1]; lastDiff = pre[i] - pre[size - 1]; if (nextDiff * lastDiff < 0) { return false ; }; } return true ; } // Driver code public static void Main(String[] args) { BinaryTree tree = new BinaryTree(); int []pre = new int []{8, 3, 5, 7, 6}; int size = pre.Length; if (tree.hasOnlyOneChild(pre, size) == true ) { Console.WriteLine( "Yes" ); } else { Console.WriteLine( "No" ); } } } // This code is contributed by aashish1995 |
Javascript
<script> // Check if each internal node of BST has only one child function hasOnlyOneChild(pre, size) { var nextDiff, lastDiff; for ( var i = 0; i < size - 1; i++) { nextDiff = pre[i] - pre[i + 1]; lastDiff = pre[i] - pre[size - 1]; if (nextDiff * lastDiff < 0) { return false ; }; } return true ; } // Driver code var pre = [8, 3, 5, 7, 6]; var size = pre.length; if (hasOnlyOneChild(pre, size) == true ) { document.write( "Yes" ); } else { document.write( "No" ); } // This code is contributed by itsok. </script> |
输出：
Yes
方法3 1.扫描preorder的最后两个节点，并将其标记为min&max。 2.扫描预订单阵列中的每个节点。每个节点必须小于最小节点或大于最大节点。相应地更新最小值和最大值。
C++
#include <bits/stdc++.h> using namespace std; int hasOnlyOneChild( int pre[], int size) { // Initialize min and max using last two elements int min, max; if (pre[size - 1] > pre[size - 2]) { max = pre[size - 1]; min = pre[size - 2]; } else { max = pre[size - 2]; min = pre[size - 1]; } // Every element must be either smaller // than min or greater than max for ( int i = size - 3; i >= 0; i--) { if (pre[i] < min) min = pre[i]; else if (pre[i] > max) max = pre[i]; else return false ; } return true ; } // Driver code int main() { int pre[] = { 8, 3, 5, 7, 6 }; int size = sizeof (pre) / sizeof (pre[0]); if (hasOnlyOneChild(pre,size)) cout << "Yes" ; else cout << "No" ; return 0; } // This code is contributed by shivanisinghss2110 |
C
#include <stdio.h> int hasOnlyOneChild( int pre[], int size) { // Initialize min and max using last two elements int min, max; if (pre[size-1] > pre[size-2]) { max = pre[size-1]; min = pre[size-2]; } else { max = pre[size-2]; min = pre[size-1]; } // Every element must be either smaller than min or // greater than max for ( int i=size-3; i>=0; i--) { if (pre[i] < min) min = pre[i]; else if (pre[i] > max) max = pre[i]; else return false ; } return true ; } // Driver program to test above function int main() { int pre[] = {8, 3, 5, 7, 6}; int size = sizeof (pre)/ sizeof (pre[0]); if (hasOnlyOneChild(pre,size)) printf ( "Yes" ); else printf ( "No" ); return 0; } |
JAVA
// Check if each internal node of BST has only one child class BinaryTree { boolean hasOnlyOneChild( int pre[], int size) { // Initialize min and max using last two elements int min, max; if (pre[size - 1 ] > pre[size - 2 ]) { max = pre[size - 1 ]; min = pre[size - 2 ]; } else { max = pre[size - 2 ]; min = pre[size - 1 ]; } // Every element must be either smaller than min or // greater than max for ( int i = size - 3 ; i >= 0 ; i--) { if (pre[i] < min) { min = pre[i]; } else if (pre[i] > max) { max = pre[i]; } else { return false ; } } return true ; } public static void main(String[] args) { BinaryTree tree = new BinaryTree(); int pre[] = new int []{ 8 , 3 , 5 , 7 , 6 }; int size = pre.length; if (tree.hasOnlyOneChild(pre, size) == true ) { System.out.println( "Yes" ); } else { System.out.println( "No" ); } } } // This code has been contributed by Mayank Jaiswal |
Python3
# Check if each internal # node of BST has only one child # approach 2 def hasOnlyOneChild(pre,size): # Initialize min and max # using last two elements min = 0 ; max = 0 if pre[size - 1 ] > pre[size - 2 ] : max = pre[size - 1 ] min = pre[size - 2 ] else : max = pre[size - 2 ] min = pre[size - 1 ] # Every element must be # either smaller than min or # greater than max for i in range (size - 3 , 0 , - 1 ): if pre[i] < min : min = pre[i] elif pre[i] > max : max = pre[i] else : return False return True # Driver program to # test above function if __name__ = = "__main__" : pre = [ 8 , 3 , 5 , 7 , 6 ] size = len (pre) if (hasOnlyOneChild(pre, size)): print ( "Yes" ) else : print ( "No" ) # This code is contributed by # Harshit Saini |
C#
// Check if each internal node of BST has only one child using System; public class BinaryTree { bool hasOnlyOneChild( int []pre, int size) { // Initialize min and max using last two elements int min, max; if (pre[size - 1] > pre[size - 2]) { max = pre[size - 1]; min = pre[size - 2]; } else { max = pre[size - 2]; min = pre[size - 1]; } // Every element must be either smaller than min or // greater than max for ( int i = size - 3; i >= 0; i--) { if (pre[i] < min) { min = pre[i]; } else if (pre[i] > max) { max = pre[i]; } else { return false ; } } return true ; } // Driver code public static void Main(String[] args) { BinaryTree tree = new BinaryTree(); int []pre = new int []{8, 3, 5, 7, 6}; int size = pre.Length; if (tree.hasOnlyOneChild(pre, size) == true ) { Console.WriteLine( "Yes" ); } else { Console.WriteLine( "No" ); } } } // This code is contributed by aashish1995 |
Javascript
<script> // Check if each internal node of BST // has only one child class BinaryTree { hasOnlyOneChild(pre, size) { // Initialize min and max using // last two elements var min, max; if (pre[size - 1] > pre[size - 2]) { max = pre[size - 1]; min = pre[size - 2]; } else { max = pre[size - 2]; min = pre[size - 1]; } // Every element must be either // smaller than min or // greater than max for ( var i = size - 3; i >= 0; i--) { if (pre[i] < min) { min = pre[i]; } else if (pre[i] > max) { max = pre[i]; } else { return false ; } } return true ; } } // Driver code var tree = new BinaryTree(); var pre = [8, 3, 5, 7, 6]; var size = pre.length; if (tree.hasOnlyOneChild(pre, size) == true ) { document.write( "Yes" ); } else { document.write( "No" ); } </script> |
输出：
Yes
如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
