给定二叉搜索树的前序遍历。然后，任务是从给定的前序打印二叉搜索树的叶节点。
null
例如：
Input : preorder[] = {890, 325, 290, 530, 965};Output : 290 530 965Tree represented is, 890 / 325 965 / 290 530Input : preorder[] = { 3, 2, 4 };Output : 2 4
本文讨论了一个简单的递归解决方案。其思想是使用两个min和max变量，并取i（输入数组中的索引），即给定预排序数组的索引，递归地创建根节点，并相应地检查左和右是否存在。这个方法返回布尔变量，如果left和right都为false，则表示left和right都为null，因此它必须是一个叶节点，所以在那里打印它，并在该索引存在根时返回true。
C++
// Recursive C++ program to find leaf // nodes from given preorder traversal #include<bits/stdc++.h> using namespace std; // Print the leaf node from // the given preorder of BST. bool isLeaf( int pre[], int &i, int n, int min, int max) { if (i >= n) return false ; if (pre[i] > min && pre[i] < max) { i++; bool left = isLeaf(pre, i, n, min, pre[i-1]); bool right = isLeaf(pre, i, n, pre[i-1], max); if (!left && !right) cout << pre[i-1] << " " ; return true ; } return false ; } void printLeaves( int preorder[], int n) { int i = 0; isLeaf(preorder, i, n, INT_MIN, INT_MAX); } // Driver code int main() { int preorder[] = { 890, 325, 290, 530, 965 }; int n = sizeof (preorder)/ sizeof (preorder[0]); printLeaves(preorder, n); return 0; } |
JAVA
// Recursive Java program to find leaf // nodes from given preorder traversal class GFG { static int i = 0 ; // Print the leaf node from // the given preorder of BST. static boolean isLeaf( int pre[], int n, int min, int max) { if (i >= n) { return false ; } if (pre[i] > min && pre[i] < max) { i++; boolean left = isLeaf(pre, n, min, pre[i - 1 ]); boolean right = isLeaf(pre, n, pre[i - 1 ], max); if (!left && !right) { System.out.print(pre[i - 1 ] + " " ); } return true ; } return false ; } static void printLeaves( int preorder[], int n) { isLeaf(preorder, n, Integer.MIN_VALUE, Integer.MAX_VALUE); } // Driver code public static void main(String[] args) { int preorder[] = { 890 , 325 , 290 , 530 , 965 }; int n = preorder.length; printLeaves(preorder, n); } } // This code contributed by Rajput-Ji |
Python3
# Recursive Python program to find leaf # nodes from given preorder traversal # Print the leaf node from # the given preorder of BST. def isLeaf(pre, i, n, Min , Max ): if i[ 0 ] > = n: return False if pre[i[ 0 ]] > Min and pre[i[ 0 ]] < Max : i[ 0 ] + = 1 left = isLeaf(pre, i, n, Min , pre[i[ 0 ] - 1 ]) right = isLeaf(pre, i, n, pre[i[ 0 ] - 1 ], Max ) if left = = False and right = = False : print (pre[i[ 0 ] - 1 ], end = " " ) return True return False def printLeaves(preorder, n): i = [ 0 ] INT_MIN, INT_MAX = - 999999999999 , 999999999999 isLeaf(preorder, i, n, INT_MIN, INT_MAX) # Driver code if __name__ = = '__main__' : preorder = [ 890 , 325 , 290 , 530 , 965 ] n = len (preorder) printLeaves(preorder, n) # This code is contributed by PranchalK |
C#
// Recursive C# program to find leaf // nodes from given preorder traversal using System; class GFG { static int i = 0; // Print the leaf node from // the given preorder of BST. static bool isLeaf( int []pre, int n, int min, int max) { if (i >= n) { return false ; } if (pre[i] > min && pre[i] < max) { i++; bool left = isLeaf(pre, n, min, pre[i - 1]); bool right = isLeaf(pre, n, pre[i - 1], max); if (!left && !right) { Console.Write(pre[i - 1] + " " ); } return true ; } return false ; } static void printLeaves( int []preorder, int n) { isLeaf(preorder, n, int .MinValue, int .MaxValue); } // Driver code public static void Main(String[] args) { int []preorder = {890, 325, 290, 530, 965}; int n = preorder.Length; printLeaves(preorder, n); } } // This code is contributed by princiraj1992 |
PHP
<?php // Recursive PHP program to // find leaf nodes from given // preorder traversal // Print the leaf node from // the given preorder of BST. function isLeaf( $pre , & $i , $n , $min , $max ) { if ( $i >= $n ) return false; if ( $pre [ $i ] > $min && $pre [ $i ] < $max ) { $i ++; $left = isLeaf( $pre , $i , $n , $min , $pre [ $i - 1]); $right = isLeaf( $pre , $i , $n , $pre [ $i - 1], $max ); if (! $left && ! $right ) echo $pre [ $i - 1] , " " ; return true; } return false; } function printLeaves( $preorder , $n ) { $i = 0; isLeaf( $preorder , $i , $n , PHP_INT_MIN, PHP_INT_MAX); } // Driver code $preorder = array (890, 325, 290, 530, 965 ); $n = sizeof( $preorder ); printLeaves( $preorder , $n ); // This code is contributed by ajit ?> |
Javascript
<script> // Recursive Javascript program to find leaf // nodes from given preorder traversal let i = 0; // Print the leaf node from // the given preorder of BST. function isLeaf(pre, n, min, max) { if (i >= n) { return false ; } if (pre[i] > min && pre[i] < max) { i++; let left = isLeaf(pre, n, min, pre[i - 1]); let right = isLeaf(pre, n, pre[i - 1], max); if (!left && !right) { document.write(pre[i - 1] + " " ); } return true ; } return false ; } function printLeaves(preorder, n) { isLeaf(preorder, n, Number.MIN_VALUE, Number.MAX_VALUE); } // Driver code let preorder = [ 890, 325, 290, 530, 965 ]; let n = preorder.length; printLeaves(preorder, n); // This code is contributed by divyeshrabadiya07 </script> |
输出：
290 530 965
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
