My accepted Java code with one stack and LR tags

  • 0

    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'){
        		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.