Iterative O(n) java solution without using stack. 1ms


  • 0
    S
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
    	List<TreeNode> rights = new ArrayList<>();
    	int ind = -1;
    	TreeNode curr = root;
    	
    	while(curr!=null){
    		res.add(curr.val);
    		if(curr.right!=null){
    			ind++;
    			rights.add(ind,curr.right);
    		}
    		if(curr.left!=null){
    			curr = curr.left;
    		}
    		else{
    			curr = ind<0?null:rights.get(ind);
    			ind--;
    		}		
    	}
    			
        return res;
    }

  • 0
    H

    I think you are actually using a stack implemented by List.


  • 0
    S

    I would say, I implemented stack logic using List.
    This is not the same


Log in to reply
 

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