Java 中从 BST 的先序遍历中显示叶节点

2024年9月10日 | 11 分钟阅读

给定一个输入数组。该输入数组是二叉搜索树 (BST) 的先序遍历。任务是检测并打印二叉搜索树的叶子节点。叶子节点是树中没有子节点的节点。

示例 1

输入

int preorderArr[] = {25, 20, 10, 5, 12, 22, 36, 30, 28, 40, 38, 48}

输出 {5, 12, 22, 28, 38, 48}

解释： 节点值 5、12、22、28、38 和 48 是叶子节点。

示例 2

输入

int preorderArr[] = {891, 326, 291, 531, 966}

输出 {291, 531, 966}

解释： 节点值 291、531 和 966 是叶子节点。

简单方法

简单或朴素的方法是进行一次额外的遍历。我们知道，如果我们从三者（中序、先序和后序）中获得任何两个遍历，我们就可以得到二叉树，然后从中可以轻松得到叶子节点。先序遍历已经给出。因此，我们的任务是找到后序遍历或中序遍历。我们知道，如果我们对二叉搜索树进行中序遍历，我们会按照排序的顺序得到节点的值（BST 的属性）。

因此，我们所要做的就是创建一个名为 inorderArr[] 的数组。将 preorderArr 的所有元素复制到其中并对 inorderArr[] 数组进行排序。现在，我们得到了两个遍历（一个是先序，另一个是中序）。我们所要做的就是从这两个遍历构建一个二叉搜索树，然后找到其中的叶子节点并显示它。以下程序使概念更加清晰。

文件名： DisplayLeafBST.java

// importing Arrays and ArrayList that are
// required in the program
import java.util.Arrays;
import java.util.ArrayList;

// a class for creating nodes of the Binary Search Tree
class TreeNode 
{
// for holding the value of the node
int val;

// for holding the left child
TreeNode left;

// for holding the right child
TreeNode right;

// constructor of the class 
TreeNode(int x) 
{
val = x;
left = null;
right = null;
}
}


public class DisplayLeafBST
{
// a method that displays the leaf nodes of the Binary Search Tree
public void displayLeafNodes(ArrayList<Integer> leafNodeList)
{
int size = leafNodeList.size();

for(int i = 0 ; i < size; i++)
{
System.out.print(leafNodeList.get(i) + " "); 
}
}


// a method that creates inorder traversal of a Binary Search Tree
// whose preorder traversal is given to us.
public int[] createInorder(int preorderArr[])
{

// computing the size of the preorderArr
int size = preorderArr.length;


// for storing the inorder traversal
int inorderArr[] = new int[size];


// copying the values in the array inorderArr[]
for(int i = 0; i < size; i++)
{
inorderArr[i] = preorderArr[i];     
}

// sorting to get the inorder
Arrays.sort(inorderArr);

return inorderArr;
}

public TreeNode createBST(int preorderArr[],int start1, int end1, int inorderArr[],int start2, int end2)
{
// handling the base case
if(start2 > end2)
{ 
return null;
}


// only one element is left, therefore create a node
// for it and return
if(start2 == end2)
{
return new TreeNode(inorderArr[end2]);
}


// creating the root node. The root node of the tree is  
// the first element of the array preorderArr[]
TreeNode root = new TreeNode(preorderArr[start1]);

// start looking for the root value in the array inorderArr
int j = start2;
for(; j <= end2; j++)
{
if(inorderArr[j] == preorderArr[start1])
{
// when the value is found
// terminate the loop using a break statement
break;
}
}

// values from start2 to j - 1 of the array inorderArr are the elements of the left subtree 
// values from j + 1 to end2 of the array inorderArr are the elements of the right subtree
// We need to separate the elements of the array preorderArr for the left and right subtrees 
// start1 + 1 to start1 + j - start2 are the elements of the left subtree
// start1 + j - start2 + 1 to end2 are the elements of the right subtree

// recursively constructing the Binary Search Tree using the preorerArr and inorderArr

// constructing the left subtree
root.left = createBST(preorderArr, start1 + 1, start1 + j - start2, inorderArr, start2, j - 1);

// constructing the right subtree
root.right = createBST(preorderArr, start1 + j - start2 + 1, end2, inorderArr, j + 1, end2);

// returning the root node
return root;
}


public void findLeafNodes(TreeNode rt, ArrayList<Integer> leafNodeList)
{
// handling the base case
if(rt == null)
{
return;
}

// if a node has its left and right child as null
// then it means that node is a leaf node, and we have
// to store the value of that leaf node in the leafNodeList
if(rt.left == null && rt.right == null)
{
leafNodeList.add(rt.val);

return;
}

// recursively finding the leaf nodes

// recursion towards the left child
findLeafNodes(rt.left, leafNodeList);

// recursion towards the right child
findLeafNodes(rt.right, leafNodeList);

}


// main method
public static void main(String argvs[]) 
{

// creating an object of the class DisplayLeafBST
DisplayLeafBST obj = new DisplayLeafBST();

// input 1
int preorderArr[] = {25, 20, 10, 5, 12, 22, 36, 30, 28, 40, 38, 48};
int size = preorderArr.length;


System.out.println("For a Binary Search Tree that has the preorder traversal as: " );
for(int k = 0; k < size; k++)
{
System.out.print(preorderArr[k] + " ");
}
System.out.println( "\n" );

// storing the inorder traversal
int inorderArr[] = obj.createInorder(preorderArr);

// invoking the method createBST() and storing the root node
TreeNode rt = obj.createBST(preorderArr, 0, size - 1, inorderArr, 0, size - 1);

// an array list for storing the leaf nodes
ArrayList<Integer> leafNodeList = new ArrayList<Integer>();
obj.findLeafNodes(rt, leafNodeList);
System.out.println("The leaf nodes are: " );
obj.displayLeafNodes(leafNodeList);

System.out.println( "\n" );

// input 2
int preorderArr1[] = {891, 326, 291, 531, 966};
size = preorderArr1.length;


System.out.println("For a Binary Search Tree that has the preorder traversal as: " );
for(int k = 0; k < size; k++)
{
System.out.print(preorderArr1[k] + " ");
}
System.out.println( "\n" );

// storing the inorder traversal
int inorderArr1[] = obj.createInorder(preorderArr1);

// invoking the method createBST() and storing the root node
rt = obj.createBST(preorderArr1, 0, size - 1, inorderArr1, 0, size - 1);

// an array list for storing the leaf nodes
leafNodeList = new ArrayList<Integer>();
obj.findLeafNodes(rt, leafNodeList);
System.out.println("The leaf nodes are: " );
obj.displayLeafNodes(leafNodeList);

}


}

输出

For a Binary Search Tree that has the preorder traversal as: 
25 20 10 5 12 22 36 30 28 40 38 48 

The leaf nodes are: 
5 12 22 28 38 48 

For a Binary Search Tree that has the preorder traversal as: 
891 326 291 531 966 

The leaf nodes are: 
291 531 966

复杂度分析： createBST() 方法需要 O(n2) 的时间来构建二叉搜索树。其他方法也需要时间来产生结果。然而，createBST() 方法消耗的时间最多。因此，程序的总体时间复杂度为 O(n2)。此外，程序使用一个辅助数组来存储叶子节点以及中序遍历。因此，空间复杂度为 O(n)，其中 n 是 preorderArr[] 数组中的元素总数。

优化： 如果我们观察，会发现上面的程序中不需要 createBST() 方法。无需创建二叉搜索树，我们就可以轻松找到叶子节点。此外，在 inorderArr[] 中搜索元素不需要线性搜索。这是因为 inorderArr[] 是已排序的。因此，我们也可以进行二分搜索。它会将时间复杂度从 O(n) 降低到 O(log(n))。请看下面的程序。

文件名： DisplayLeafBST1.java

// importing Arrays that are
// required in the program
import java.util.Arrays;


public class DisplayLeafBST1
{

// a method that finds the element ele in the array inorderArr and returns its index
public int binrySearch(int inorderArr[], int start1, int end1, int ele)
{
int midIndx = (start1 + end1) >> 1;

// element is found in the array inorderArr[]. Hence, return its index
if (inorderArr[midIndx] == ele)
{
return midIndx;
}

// the element is lesser than the middle element of the array inorderArr[]
// Hence, reduce the value of the middle index by 1
else if (inorderArr[midIndx] > ele)
{
return binrySearch(inorderArr, start1, midIndx - 1, ele);
}

// the element is more than the middle element of the array inorderArr[]
// Hence, increase the value of the middle index by 1
else
{
return binrySearch(inorderArr, midIndx + 1, end1, ele);
}
}

// a method that creates inorder traversal of a Binary Search Tree
// whose preorder traversal is given to us.
public int[] createInorder(int preorderArr[])
{

// computing the size of the preorderArr
int size = preorderArr.length;


// for storing the inorder traversal
int inorderArr[] = new int[size];


// copying the values in the array inorderArr[]
for(int i = 0; i < size; i++)
{
inorderArr[i] = preorderArr[i];     
}

// sorting to get the inorder
Arrays.sort(inorderArr);

return inorderArr;
}
static int indx = 0;

public void leafNodesRecursion(int preorderArr[], int inorderArr[], int start1, int end1, int size)
{
// If start1 == end1, hence there is no left or right subtree.
// So, it has to be a leaf Node. Therefore, display its value.
if(start1 == end1)
{
System.out.printf("%d ", inorderArr[start1]);
indx = indx + 1;
return;
}

// either start1 or end1 has gone beyond the size of the array. Hence, return.
if (start1 < 0 || start1 > end1 || end1 >= size)
{
return;
}

// looking for the index of the element present in preorderArr
// in the array inorderArr with the help of binary search.
int loccation = binrySearch(inorderArr, start1, end1, preorderArr[indx]);

// Increasing the index by 1
indx = indx + 1;

// looking in the left subtree.
leafNodesRecursion(preorderArr, inorderArr, start1, loccation - 1, size);

// looking in the right subtree.
leafNodesRecursion(preorderArr, inorderArr, loccation + 1, end1, size);
}



// main method
public static void main(String argvs[]) 
{

// creating an object of the class DisplayLeafBST1
DisplayLeafBST1 obj = new DisplayLeafBST1();

// input 1
int preorderArr[] = {25, 20, 10, 5, 12, 22, 36, 30, 28, 40, 38, 48};
int size = preorderArr.length;


System.out.println("For a Binary Search Tree that has the preorder traversal as: " );
for(int k = 0; k < size; k++)
{
System.out.print(preorderArr[k] + " ");
}
System.out.println( "\n" );

// storing the inorder traversal
int inorderArr[] = obj.createInorder(preorderArr);

System.out.println("The leaf nodes are: " );
obj.leafNodesRecursion(preorderArr, inorderArr, 0, size - 1, size);

System.out.println( "\n" );

// input 2
int preorderArr1[] = {891, 326, 291, 531, 966};
size = preorderArr1.length;

indx = 0; // resetting its value to zero for this input
System.out.println("For a Binary Search Tree that has the preorder traversal as: " );
for(int k = 0; k < size; k++)
{
System.out.print(preorderArr1[k] + " ");
}
System.out.println( "\n" );

// storing the inorder traversal
int inorderArr1[] = obj.createInorder(preorderArr1);

System.out.println("The leaf nodes are: " );
obj.leafNodesRecursion(preorderArr1, inorderArr1, 0, size - 1, size);


}


}

输出

For a Binary Search Tree that has the preorder traversal as: 
25 20 10 5 12 22 36 30 28 40 38 48 

The leaf nodes are: 
5 12 22 28 38 48 

For a Binary Search Tree that has the preorder traversal as: 
891 326 291 531 966 

The leaf nodes are: 
291 531 966

复杂度分析： leafNodesRecursion() 方法需要 O(n) 时间。在每次递归调用中，我们都会调用 binrySearch() 方法，该方法需要 O(log(n)) 时间。因此，程序的总体时间复杂度为 O(n x log(n))，其中 n 是 preorderArr[] 数组中的元素总数。程序的空间复杂度与前一个程序相同。

让我们进行更多优化以降低时间复杂度。

方法：使用栈

利用堆栈和二叉搜索树的属性，可以降低程序的时空复杂度。首先，我们需要使用两个指针 m 和 n 来遍历 preorderArr[]。最初，m = 0，n = 1。当 preorderArr[m] > preorderArr[n] 时，我们可以得出 preorderArr[n] 是 preorderArr[m] 的左子节点。我们知道先序遍历遵循根 -> 左 -> 右的模式。因此，元素 preorderArr[m] 被压入堆栈。

对于那些不实现 BST 规则的节点，需要从堆栈中移除元素，直到 preorderArr[m] 大于堆栈的顶部元素，并在不大于时中断循环，然后显示相应的 m 值。

文件名： DisplayLeafBST1.java

// importing Arrays that are
// required in the program
import java.util.Stack;


public class DisplayLeafBST2
{

// a method that finds out and prints the values of leaf nodes 
public void findPrintLeafNodes(int preorderArr[], int size)
{

Stack<Integer> s = new Stack<Integer> ();
for (int m = 0, n = 1; n < size; m++, n++)
{
boolean isFound = false;

// first of all, we traverse the left subtree of the Binary Search Tree.
// all the other nodes except the node of the minimum value in the 
// left subtree is pushed to the stack.
if(preorderArr[m] > preorderArr[n])
{
s.push(preorderArr[m]);
}

else
{
while (!s.isEmpty())
{
if (preorderArr[n] > s.peek())
{
// if we reach here, then it means that preorderArr[m] is a leaf node
s.pop();
isFound = true;
}
else
{
break;
}
}
}

if (isFound)
{
System.out.print(preorderArr[m] + " ");
}
}

// The rightmost element is always going to be a leaf node.
System.out.println(preorderArr[size - 1]);

}


// main method
public static void main(String argvs[]) 
{

// creating an object of the class DisplayLeafBST2
DisplayLeafBST2 obj = new DisplayLeafBST2();

// input 1
int preorderArr[] = {25, 20, 10, 5, 12, 22, 36, 30, 28, 40, 38, 48};
int size = preorderArr.length;


System.out.println("For a Binary Search Tree that has the preorder traversal as: " );
for(int k = 0; k < size; k++)
{
System.out.print(preorderArr[k] + " ");
}
System.out.println( "\n" );

System.out.println("The leaf nodes are: " );
obj.findPrintLeafNodes(preorderArr, size);

System.out.println( "\n" );

// input 2
int preorderArr1[] = {891, 326, 291, 531, 966};
size = preorderArr1.length;

System.out.println("For a Binary Search Tree that has the preorder traversal as: " );
for(int k = 0; k < size; k++)
{
System.out.print(preorderArr1[k] + " ");
}
System.out.println( "\n" );

System.out.println("The leaf nodes are: " );
obj.findPrintLeafNodes(preorderArr1, size);


}


}

输出

For a Binary Search Tree that has the preorder traversal as: 
25 20 10 5 12 22 36 30 28 40 38 48 

The leaf nodes are: 
5 12 22 28 38 48


For a Binary Search Tree that has the preorder traversal as: 
891 326 291 531 966 

The leaf nodes are: 
291 531 966

复杂度分析： 节点最多被遍历两次。因此，程序的时空复杂度为 O(n)。程序使用堆栈来存储元素。因此，空间复杂度与前一个程序相同。

下一个主题Java 中的运算符 Unicode

← 上一个下一个 →

Java 中从 BST 的先序遍历中显示叶节点

简单方法

方法：使用栈

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中从 BST 的先序遍历中显示叶节点

简单方法

方法：使用栈

相关帖子

Java 中读取文本文件的不同方法

Java 中的 java.util.IntSummaryStatistics 类及示例

Types of Classes in Java

Java 中的类型擦除

Java 中 & 运算符是什么

Buying Fruits Problem in Java

Java 中的 Jacobsthal 数

Java int keyword

Smith Number in Java

Control Flow in Java

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器