2021-04-03 12:08

这个怎么改为非递归形式实现？

``````import java.util.Arrays;
import java.util.Scanner;

public class Main {

private static class TreeNode {
TreeNode left;
TreeNode right;
int data;

TreeNode(int newData) {
left = null;
right = null;
data = newData;
}
}

public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int[] pre =new int[n];
for(int i=0;i<n;i++)
pre[i] =input.nextInt();
int[] in =new int[n];
for(int i=0;i<n;i++)
in[i] =input.nextInt();
input.close();
TreeNode treeNode = reConstructBinaryTree(pre, in);
prePost(treeNode);

}

public static TreeNode reConstructBinaryTree(int [] pre,int [] in) {

if(pre.length == 0 || in.length == 0)
return null;
TreeNode root = new TreeNode(pre[0]);
for (int i = 0; i < in.length; i++) {
if(in[i] == pre[0]){
//左子树,copyOfRange函数是左闭右开
root.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));
//递归构建左子树
root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length));
break;
}
}
return root;
}

public static void prePost(TreeNode root){
if(root == null)
System.out.println("空树");

if(root.left != null)
prePost(root.left);

if(root.right!= null)
prePost(root.right);
System.out.print(root.data+" ");
}
}``````
• 写回答
• 好问题 提建议
• 追加酬金
• 关注问题
• 邀请回答

3条回答默认 最新

• allway2 2021-04-03 20:10
最佳回答
``````
import java.util.Arrays;
import java.util.Deque;
import java.util.Scanner;

public class Main2 {

private static class TreeNode {

TreeNode left;

TreeNode right;

int data;

TreeNode(int newData) {

left = null;

right = null;

data = newData;

}

}

public static void main(String[] args) {

Scanner input = new Scanner(System.in);

int n = input.nextInt();

int[] pre = new int[n];

for (int i = 0; i < n; i++)

pre[i] = input.nextInt();

int[] in = new int[n];

for (int i = 0; i < n; i++)

in[i] = input.nextInt();

input.close();

TreeNode treeNode = reConstructBinaryTree(pre, in);

prePost(treeNode);

}

public static TreeNode reConstructBinaryTree(int[] pre, int[] in) {

if (pre == null || pre.length == 0) {
return null;
}
TreeNode root = new TreeNode(pre[0]);
stack.push(root);
int inorderIndex = 0;
for (int i = 1; i < pre.length; i++) {
int preorderVal = pre[i];
TreeNode node = stack.peek();
if (node.data != in[inorderIndex]) {
node.left = new TreeNode(preorderVal);
stack.push(node.left);
} else {
while (!stack.isEmpty() && stack.peek().data == in[inorderIndex]) {
node = stack.pop();
inorderIndex++;
}
node.right = new TreeNode(preorderVal);
stack.push(node.right);
}
}
return root;
}

public static void prePost(TreeNode root) {

if (root == null)

System.out.println("空树");

if (root.left != null)

prePost(root.left);

if (root.right != null)

prePost(root.right);

System.out.print(root.data + " ");

}

}``````
评论
解决 1 无用
打赏 举报