weixin_47019501
2021-04-03 12:08
采纳率: 100%
浏览 29
已采纳

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

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.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 + " ");
    
    	}
    
    }
    评论
    解决 1 无用
    打赏 举报
查看更多回答(2条)

相关推荐 更多相似问题