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

Question

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+" ");
    }
}

Answer 1

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
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]);
		Deque<TreeNode> stack = new LinkedList<TreeNode>();
		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 + " ");

	}

}

Answer 2

谢谢