Share my iterative java solution


  • 2
    B
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        TreeNode root=null;
    	if(preorder.length!=inorder.length)
    		return root;
    	
    	HashMap<Integer,Integer> map=new HashMap<>();
    	for(int i=0;i<inorder.length;i++)
    		map.put(inorder[i], i);
    
    	TreeNode p=root;
    	Stack<TreeNode> tree=new Stack<>();
    	
    	for(int i=0;i<preorder.length;i++){
    		int temp=map.get(preorder[i]);
    		TreeNode node=new TreeNode(preorder[i]);
    		if(tree.isEmpty()){
    			root=node;
    			tree.add(node);
    			p=root;
    		}
    		else {
    			if(temp<map.get(tree.peek().val)){
    				p.left=node;
    				p=p.left;
    			}
    			else {
    				while(!tree.isEmpty()&&temp>map.get(tree.peek().val))
    					p=tree.pop();
    				p.right=node;
    				p=p.right;
    			}
    		}
    		tree.add(node);
    	}
    	return root;
        
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.