My accepted Java code with one stack and LR tags


  • 0
    Z

    I write a new Class TreeNodeFlag to save the node and a tag. Here is my thought: When 'temp' points to a new node, it will push a new instance of TreeNodeFlag which saves the node 'temp' and a tag 'L'.Then let temp point to its left child. When temp == null, check the top element of the stack, if the tag is 'L', then point to its right child. In brief, a tag 'L' or 'R' controls temp pointing to its left or right child. I hope my expression is intuitive for you. My English is not so good ^_^

        ArrayList<Integer> list = new  ArrayList<Integer>();
        
        Stack<TreeNodeFlag> s = new Stack<TreeNodeFlag>();
        TreeNode temp = root;
        
        while(temp != null || !s.isEmpty()){
        	while(temp != null){
        		s.add(new TreeNodeFlag(temp, 'L'));
        		temp = temp.left;
        	}
        	
        	while(!s.isEmpty() && s.peek().tags == 'R'){
        		list.add(s.pop().node.val);
        	}
        	
        	if(!s.isEmpty()){
        		TreeNodeFlag f = s.peek();
        		temp = f.node.right;
        		f.tags = 'R';
        	}
        	
        }
    	return list;
    

    class TreeNodeFlag{
    public TreeNode node;
    public char tags;
    public String path;

    public TreeNodeFlag(TreeNode node, char tags){
    	this.node = node;
    	this.tags = tags;
    }
    

    }


Log in to reply
 

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