我正在研究从gfg BST到最大堆的代码挑战：
给定一个二进制搜索树。将给定的BST转换为特殊最大堆，条件是节点左子树中的所有值都应小于节点右子树中的全部值。此条件应用于如此转换的最大堆中的所有节点。
我无法解决挑战。
因此，我查看了以下解决方案代码：
class Solution
{
public static ArrayList<Integer> list=new ArrayList<>();
static int i=0;
public static void InOrderTraversal(Node root){
if(root == null) return ;
InOrderTraversal(root.left);
list.add(root.data);
InOrderTraversal(root.right);
}
public static void PostOrderTraversal(Node root){
if(root == null )return;
PostOrderTraversal(root.left);
PostOrderTraversal(root.right);
root.data= list.get(i);
i++;
}
public static void convertToMaxHeapUtil(Node root)
{
InOrderTraversal(root);
PostOrderTraversal(root);
}
}
我看不出这段代码如何改变树的结构，因为它既不添加也不删除任何节点。以下是从gfg官方网站复制的第二个示例测试用例：
输入BST:
3
/
1 5
/
2 4 6
7
预期最大堆输出：
7
/
3 6
/ /
1 2 4 5
我不明白它是如何处理那个测试用例的。
问题的驱动程序代码：
//{ Driver Code Starts
//Initial Template for Java
import java.util.LinkedList;
import java.util.Queue;
import java.io.*;
import java.util.*;
class Node{
int data;
Node left;
Node right;
Node(int data){
this.data = data;
left=null;
right=null;
}
}
class Tree {
static Node buildTree(String str){
if(str.length()==0 || str.charAt(0)=='N'){
return null;
}
String ip[] = str.split(" ");
// Create the root of the tree
Node root = new Node(Integer.parseInt(ip[0]));
// Push the root to the queue
Queue<Node> queue = new LinkedList<>();
queue.add(root);
// Starting from the second element
int i = 1;
while(queue.size()>0 && i < ip.length) {
// Get and remove the front of the queue
Node currNode = queue.peek();
queue.remove();
// Get the current node's value from the string
String currVal = ip[i];
// If the left child is not null
if(!currVal.equals("N")) {
// Create the left child for the current node
currNode.left = new Node(Integer.parseInt(currVal));
// Push it to the queue
queue.add(currNode.left);
}
// For the right child
i++;
if(i >= ip.length)
break;
currVal = ip[i];
// If the right child is not null
if(!currVal.equals("N")) {
// Create the right child for the current node
currNode.right = new Node(Integer.parseInt(currVal));
// Push it to the queue
queue.add(currNode.right);
}
i++;
}
return root;
}
static void postOrder(Node root)
{
if(root == null)
return;
postOrder(root.left);
postOrder(root.right);
System.out.print(root.data+" ");
}
public static void main (String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t=Integer.parseInt(br.readLine());
while(t > 0){
String s = br.readLine();
Node root = buildTree(s);
Solution g = new Solution();
g.convertToMaxHeapUtil(root);
postOrder(root);
System.out.println();
t--;
}
}
}
// } Driver Code Ends
您提供的代码解决了这个问题，因为输出树不需要是一个完整的二进制树。尽管示例输出显示了一个完整的二进制树作为输出，但这不是代码挑战的要求。自动测试将仅验证输出中树的所有子节点的值是否小于其父节点的值。它不会验证树的形状。
这个解决方案的作者有洞察力，只需保持树的形状不变，所有节点都保持在原来的位置，并且只在树中的值之间移动。
实现这一点的方法很简单：首先，通过按顺序遍历将值(而不是节点！(收集在列表中。由于输入树是BST，因此列表将按排序顺序获得值。
然后，该列表中的每个值都被分配回节点的数据，覆盖它们以前的值。这一次节点是按后序访问的，这意味着父节点将比其子节点晚获得它们的值。由于列表是排序的，这意味着父节点将获得比其子节点更大的值。这正是测试套件将要测试的内容。
我们确实注意到，这可能以一种令人惊讶的方式解决了的挑战，但这不是你在实践中想要做的事情，因为如果堆不平衡，它就无法提供预期的效率。
因此，如果您一直在尝试构建一个解决方案，在该解决方案中，您可以获得高效的堆作为输出，那么我只能赞扬这一努力。这就是程序员构建堆的目标，它表明了为什么解决代码挑战并不总是有助于改进解决现实生活中的编码问题。